백준 2573 - 빙산

문제링크

• 백준 2573

문제설명

• NxM 크기의 지도 위 각 칸에 바다는 0, 빙산은 양의 정수로 높이를 나타내고 있다.
• 각각의 빙산은 동서남북으로 접하고 있는 바다의 개수 만큼 1년마다 녹는다.
• 한덩어리의 빙산이 두덩어리 이상으로 나뉘게 될때까지 몇년이 걸리는지 구하면 된다.
  • 빙산이 다 녹을때까지 나뉘어지지 않는다면 0을 출력한다.

문제접근

• BFS 혹은 DFS가 시행되는 횟수는 덩어리의 개수를 의미한다. 즉, BFS 혹은 DFS로 모든 빙산에 방문할 수 없을 때 덩어리가 분리된 상황이다.
  • 이번 풀이에서는 BFS를 사용했다.
• 빙산은 서로 독립적으로 녹아야 한다. 다시 말해, 1번 빙산이 녹아서 바다가 되었을 때 2번 빙산이 1번 빙산의 자리를 바다로 생각하면 안된다.
• 따라서, 별도의 2차원 배열(ice)을 만들어서 BFS로 모든 빙산의 높이를 갱신하고 난 후, 바다로 변한 빙산의 위치를 바다로 갱신해주도록 하였다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
using namespace std;

int N, M;
int northOcean[300][300] = { 0, };
int ice[300][300] = { 0, };; // 빙산인 곳은 1, 바다는 0
bool visited[300][300] = { false, };
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int Bfs(int xpos, int ypos) {
	queue<pair<int, int>> q;
	vector<pair<int, int>> history;
	q.push(make_pair(xpos, ypos));
	visited[xpos][ypos] = true;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		history.push_back(cpos);
		q.pop();

		// 줄어들 높이 계산
		int cnt = 0;
		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> sea;
			sea.first = cpos.first + dx[dir];
			sea.second = cpos.second + dy[dir];
			if (sea.first < 0 || sea.first >= N || sea.second < 0 || sea.second >= M) continue;
			if (ice[sea.first][sea.second] == 0) cnt++;
		}
		northOcean[cpos.first][cpos.second] -= cnt;

		// 다음에 방문할 좌표를 결정
		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
			if (ice[nextX][nextY] == 1) {
				if (visited[nextX][nextY]) continue;
				visited[nextX][nextY] = true;
				q.push(make_pair(nextX, nextY));
			}
		}
	}

	// 녹은 빙산들 중 높이가 0보다 작아 바다가 된 칸을 표시한다.
	for (auto pos : history) {
		if (northOcean[pos.first][pos.second] <= 0) {
			ice[pos.first][pos.second] = 0;
			northOcean[pos.first][pos.second] = 0;
		}
	}

	return 1;
}

int SpendYears() {
	// 빙산이 위치한 좌표를 찾는다.
	int cnt = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (northOcean[r][c] > 0 && visited[r][c]==false)
				cnt += Bfs(r, c);
		}
	}

	if (cnt > 1) return 0;
	if (cnt==1) return 1; // 한덩어리인 경우
	if (cnt == 0) return 2; // 전부다 녹은 경우
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &N, &M);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			scanf("%d", &northOcean[r][c]);
			if (northOcean[r][c] > 0) ice[r][c] = 1;
		}
	}

	int ans = 0;
	int ret;
	while (true) {
		ret = SpendYears();
		if (ret == 0) break;
		else if (ret == 2) {
			ans = 0;
			break;
		}
		memset(visited, false, sizeof(visited));
		ans++;
	}
	 printf("%d\n", ans);
	return 0;
}