[BOJ] 2573번_빙산_DFS (C++)

[문제]

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

2차원 배열로 빙산이 주어진다. 빙산의 높이는 각 칸의 숫자로 표현되며, 바다에 해당하는 칸은 0이 저장된다. 일년마다 빙산이 녹는데 빙산은 동서남북의 바다 개수만큼 줄어든다. 이때 빙산이 2개 이상으로 분리되는데 몇년 걸리는지 구하는 문제이다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• DFS를 이용해서 연결되어 있는 빙산의 개수를 구한다. 빙산의 개수가 2개 이상이면 분리된 것으로 year를 출력하고 종료한다.
• 1년이 지나면 빙산이 녹는데 배열의 앞부터 순차적으로 녹는 것이 아니라 동시에 녹아야되므로, melt배열에 빙산의 각 칸마다 얼만큼 녹아야되는지 저장해 둔 후 한번에 녹여야 된다.
• 빙산이 녹았을 때, 배열의 모든 원소가 0이되면 "만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다." 라는 조건을 충족한 것이므로 몇년이 지났더라도 year이 아닌 0을 출력한다.

[코드]

//boj2573번_빙산_그래프

#include<iostream>

using namespace std;

int graph[301][301];
int melt[301][301];
bool visited[301][301];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int N, M;

int year = 0;

void DFS(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y] && graph[next_x][next_y] != 0) {
			DFS(next_x, next_y);
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}

	while (true) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = false;
				melt[i][j] = 0;
			}
		}

		int cnt = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && graph[i][j] != 0) {
					DFS(i, j);
					cnt++;
				}
			}
		}

		if (cnt >= 2) {
			cout << year;
			return 0;
		}

		year++;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				for (int k = 0; k < 4; k++) {
					int melt_x = i + dx[k];
					int melt_y = j + dy[k];

					if (melt_x >= 0 && melt_x < N && melt_y >= 0 && melt_y < M && graph[melt_x][melt_y] == 0) {
						melt[i][j] += 1;
					}
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				graph[i][j] -= melt[i][j];
				if (graph[i][j] < 0) {
					graph[i][j] = 0;
				}
			}
		}

		bool check = false;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (graph[i][j] != 0) {
					check = true;
				}
			}
		}

		if (!check) {
			cout << 0;
			return 0;
		}
	}
}