백준 2636 치즈(bfs)

https://www.acmicpc.net/problem/2636

2636번: 치즈

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 100;
int N, M;
int graph[MAX][MAX];
bool visited[MAX][MAX];
int cheesecnt;
typedef struct
{
    int x, y;
} Air;
queue<Air> q;

typedef struct
{
    int x, y;
} Dir;
Dir dirMove[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
queue<Air> q2;
bool chk()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (graph[i][j] == 1)
                return false;
        }
    }
    return true;
}

void air_bfs()
{

    q.push({0, 0});
    q2.push({0, 0});
    visited[0][0] = true;
    while (!q.empty())
    {
        int curX = q.front().x;
        int curY = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nextX = curX + dirMove[i].x;
            int nextY = curY + dirMove[i].y;
            if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M)
            {
                if (!visited[nextX][nextY] && graph[nextX][nextY] == 0)
                {
                    q.push({nextX, nextY});
                    visited[nextX][nextY] = true;
                    q2.push({nextX, nextY});
                }
            }
        }
    }
}
void cheese_bfs()
{
    cheesecnt = 0;
    while (!q2.empty())
    {

        int curX = q2.front().x;
        int curY = q2.front().y;
        q2.pop();

        for (int i = 0; i < 4; i++)
        {
            int nextX = curX + dirMove[i].x;
            int nextY = curY + dirMove[i].y;
            if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M)
            {
                if (!visited[nextX][nextY] && graph[nextX][nextY] == 1)
                {
                    // q2.push({nextX, nextY, curCnt + 1});
                    visited[nextX][nextY] = true;
                    graph[nextX][nextY] = 0;
                    cheesecnt++;
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> graph[i][j];
        }
    }
    int cnt = 0;
    while (1)
    {
        if (chk())
        {
            cout << cnt << "\n";
            cout << cheesecnt;
            return 0;
        }
        cnt += 1;
        air_bfs();
        cheese_bfs();
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                visited[i][j] = 0;
            }
        }
    }
}

 

내가 풀었던 bfs 문제들은 항상 내부의 범위를 정하기 위해 내부에서 bfs를 돌려야 했다. 하지만, 이 문제처럼 범위의 가장자리를 도출해내기 위해서는 외부에서 bfs를 돌리면 된다. 

 

가장자리를 긁어낼때는 바깥쪽을 bfs로 돌린다는 개념을 기억하자.