[BOJ 2573] 빙산

문제 출처 : https://www.acmicpc.net/problem/2573

1. 빙산이 있는 한 곳을 시작점으로 지정한다.

2. 시작점에서 dfs로 빙산들을 돌며 몇 만큼 줄여야 하는지 저장한다.

3. dfs를 돌때 시작점에서부터 갈 수 있는 빙산의 개수를 저장한다.

4. dfs가 끝나면 먼저 시작점에서 갈 수 있는 빙산의 개수와 총 빙산의 개수를 비교하여
   만약 다르면 시간을 출력한다.

5. 빙산을 줄이고 다시 반복한다.

6. 총 빙산의 개수가 0이 되면 결국 한 덩어리로 없어진 것이므로 0을 출력한다.

#include <iostream>

#include <algorithm>

using namespace std;

int N, M, result, cnt, bing;

int map[300][300];

int first[3];

int visited[300][300][2];

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

void dfs(int i, int j)

{

visited[i][j][0] = 1; cnt++;

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

{

if ((i + dir[d][0]) >= 0 && (i + dir[d][0]) < N && (j + dir[d][1]) >= 0 && (j + dir[d][1]) <M)

{

if (map[i + dir[d][0]][j + dir[d][1]] == 0) visited[i][j][1]++;

if (map[i + dir[d][0]][j + dir[d][1]] > 0 && visited[i + dir[d][0]][j + dir[d][1]][0] != 1)

{

dfs(i + dir[d][0], j + dir[d][1]);

}

}

}

}

int main()

{

cin >> N >> M; cnt = 0; result = 0; bing = 0;

first[0] = 0;

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

{

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

{

cin >> map[i][j];

if (map[i][j] > 0 && first[0] != 0) bing++;

if (map[i][j] > 0 && first[0]==0)

{

first[1] = i; first[2] = j;

first[0] = 1; bing++;

}

visited[i][j][0] = 0; visited[i][j][1] = 0;

}

}

while (bing > 0)

{

dfs(first[1], first[2]);

if (bing != cnt)

{

cout << result << endl;

return 0;

}

first[0] = 0;

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

{

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

{

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

{

map[i][j] = map[i][j] - visited[i][j][1];

if (map[i][j] < 1)

{

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

}

if (map[i][j]>0 && first[0] == 0)

{

first[0] = 1;

first[1] = i; first[2] = j;

}

}

visited[i][j][0] = 0; visited[i][j][1] = 0;

}

}

cnt = 0; result++;

}

cout << 0 << endl;

return 0;

}