[BOJ 2638] 치즈

출처 : https://www.acmicpc.net/problem/2638

1. 외부에 0인 부분을 dfs로 돌면서 치즈에 맞닿아 있으면 치즈를 +1 증가시킨다.

2. 다 돌고 나면 치즈가 3이상인 부분이 녹는 부분이기 때문에 제거해준다.

3. 치즈가 2인 부분은 다시 1로 만들어준다.

4. 이를 반복하면서 치즈가 다 없어질때 까지 시간을 계산한다.

#include <iostream>

using namespace std;

int M, N, result, cnt;

int map[100][100];

bool visited[100][100];

int dir[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

void dfs(int m, int n)

{

for (int d = 0;d < 4;d++)

{

int nextm = m + dir[d][0]; int nextn = n + dir[d][1];

if (nextm >= 0 && nextn >= 0 && nextm < M && nextn < N

&& map[nextm][nextn] > 0) 

map[nextm][nextn] += 1;

}

visited[m][n] = true;

for (int d = 0; d < 4; d++)

{

int nextm = m + dir[d][0]; int nextn = n + dir[d][1];

if (nextm >= 0 && nextn >= 0 && nextm < M && nextn < N 

&& !visited[nextm][nextn] && map[nextm][nextn]==0)

{

dfs(nextm, nextn);

}

}

}

void cal()

{

cnt++;

dfs(0,0);

for (int i = 0; i < M; i++)

{

for (int j = 0; j < N; j++)

{

visited[i][j] = false;

if (map[i][j] > 2)

{

map[i][j] = 0; result--;

}

else if (map[i][j] == 2) map[i][j] = 1;

}

}

}

int main()

{

result = 0; cnt = 0;

cin >> M >> N;

for (int i = 0; i < M; i++)

{

for (int j = 0; j < N; j++)

{

cin >> map[i][j];

if (map[i][j] == 1) result++;

}

}

while (result > 0) cal();

cout << cnt << endl;

return 0;

}