[백준 c++] 2636 치즈

문제 설명

https://www.acmicpc.net/problem/2636
NxM 크기의 판 위에 치즈(1)가 놓여있다.
판의 가장자리에는(X) 치즈가 놓여있지 않다.
공기(0)에 접촉된 치즈(c)는 한 시간이 지나면 녹아 없어진다.
이 때 모든 치즈가 녹는데 걸리는 시간과 전부다 녹기 한 시간 전에 남아있는 치즈의 개수를 출력하는 문제다.

아이디어

공기의 영역을 구하면 된다.
판의 가장자리는 늘 치즈가 놓이지 않으므로 (0,0)부터 시작해서 DFS를 이용해서 공기의 영역을 설정해준다.

주의해야 할 것은 0이라고 해서 모두 공기의 영역이 아니다.
치즈로 둘러쌓인 0은 공기로 치지 않기 때문이다.

3:(real)공기영역 2:공기와 접촉한 치즈
1. dfs로 (0,0)부터 공기영역은 3으로 값을 바꿔준다.
2. 3과 인접한 1은 2로 바꿔준다.
3. 2,3은 0으로 바꿔준다.
4. 남은 치즈 개수가 0일 때까지 위 과정을 반복한다.

전체 코드

#include <iostream>
using namespace std;
int n, m;
int a[101][101];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void check(int y, int x)
{
    a[y][x] = 3;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if (a[ny][nx] == 0)
            check(ny, nx);
    }
    return;
}

void del(int y, int x)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if (a[ny][nx] == 3)
        {
            a[y][x] = 2; //공기 닿은 치즈로 바꾸기
            break;
        }
    }
    return;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }

    int cnt = 0;
    int past = 0;
    while (1)
    {
        int cheese = 0;
        //공기 영역 설정
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (a[i][j] == 1)
                    cheese++;
            }
        }
        check(0, 0);

        if (cheese)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (a[i][j] == 1)
                    {
                        del(i, j);
                    }
                }
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (a[i][j] == 2 || a[i][j] == 3)
                        a[i][j] = 0;
                }
            }
            past = cheese;
        }
        else
        {
            cout << cnt << "\n"
                 << past << "\n";
            break;
        }
        cnt++;
    }
}