[Algorithm] Baekjoon 2636번 : 치즈

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

2636번: 치즈

 

struct Node
{
    int y;
    int x;
};
 
int row, col;
int arr[101][101] = { 0 };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[101][101] = { false };
 
int prevMeltedCheese = 0;
int curMeltedCheese = 0;
 
void BFS() 
{
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    q.push({ 0,0 });
    visited[0][0] = true;
    int cheeseCount = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x; 
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= row) continue;
            if (nextX < 0 || nextX >= col) continue;
            if (visited[nextY][nextX] == true) continue;
 
            visited[nextY][nextX] = true;
            if (arr[nextY][nextX] == 1) // 치즈칸이면
            {
                arr[nextY][nextX] = 0;
                ++cheeseCount;
            }
            else // 빈공간이면
            {
                q.push({ nextY,nextX });
            }
        }
    }
    
    curMeltedCheese = cheeseCount;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> col;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    int hour = 0;
 
    while (1)
    {
        BFS(); // 일단 돌려서 녹은 치즈개수 체크.
 
        if (curMeltedCheese == 0) break;
 
        ++hour;
        prevMeltedCheese = curMeltedCheese;
    }
 
    cout << hour << endl << prevMeltedCheese;
}

 

제일 외각의 치즈만 계속 녹이면 되는 문제다.

즉 0,0부터 BFS로 탐색하면서 처음 만나는 치즈를 녹이고 방문표시 후, 0으로 바꿔놓는 작업만 반복하면 된다.

치즈를 녹일때마다 카운팅해주고 녹인 치즈개수가 0이라면 반복문을 탈출하고 hour와 계속 기록해놨던 이전녹은치즈개수(prevMeltedCheese)를 출력해주면 된다.