[BFS, 난이도 중상] 백준 2573번 빙산

 

지금까지 BFS를 풀어왔듯이 빙산이 몇 개의 덩어리로 되어있는지는 bfs의 while문이 끝날 때마다 1씩 추가하는 group변수의 최종 값으로 알 수 있다. bfs의 while문을 다 돌았다는 것은 덩어리 하나를 모두 방문했다는 의미다.

BFS를 수행하기 전에 빙산이 녹을 때마다 즉, 1년마다 빙산이 녹은 상태로 map배열을 바꿔주어야 한다.

 

문제 해결 흐름은

1. map배열입력

2. 1년이 지난 후의 빙산상태로 map배열을 업데이트

3. BFS로 몇 덩어리인가 계산

4. 여전히 1덩어리일 경우 과정2번으로 이동, 2덩어리 이상일 경우 정답 출력

이런 흐름으로 이루어 진다.

 

adjacent 배열은 주변에 인접한 바닷물칸의 수를 나타내는 배열이다.

map 배열에서 빙산의 높이가 0보다 작아졌을 경우에는 0으로 고정시켜주면 된다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
int map[301][301];
bool visited[301][301];
int adjacent[301][301];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	queue<pair<int, int> > q;
	int year = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	while (1) {
		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				if (map[i][j] > 0) {
					for (int k = 0; k < 4; k++) {
						if (map[i + dx[k]][j + dy[k]] == 0) adjacent[i][j]++;
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] -= adjacent[i][j];
				if (map[i][j] < 0) map[i][j] = 0;
			}
		}
		memset(adjacent, 0, sizeof(adjacent));
		int group = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] >= 1 && !visited[i][j]) {
					visited[i][j] = true;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						int x = q.front().first;
						int y = q.front().second;
						q.pop();
						for (int k = 0; k < 4; k++) {
							if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= m) continue;
							if (map[x + dx[k]][y + dy[k]] >= 1 && !visited[x + dx[k]][y + dy[k]]) {
								q.push(make_pair(x + dx[k], y + dy[k]));
								visited[x + dx[k]][y + dy[k]] = true;
							}
						}
					}
					group++;
				}
			}
		}
		memset(visited, false, sizeof(visited));
		year++;
		if (group > 1) {
			cout << year;
			return 0;
		}
		else if (group == 0) {
			cout << "0";
			return 0;
		}
	}
}