[BOJ2573] 빙산

[BOJ2573] 빙산

문제 링크

문제 설명

• 보드배열에 빙산이 있는 경우 자연수로, 빙산이 아닌 바다인 경우는 0으로 값이 주어진다. 자연수의 크기만큼 빙산의 높이가 된다.
• 빙산은 1년에 한 번 바다가 옆에 있을 때 녹는데, 4면중 바다의 개수만큼 빙산의 높이가 줄어든다.
• 처음 보드배열이 주어질 때는 하나의 빙산 덩어리로 주어지는데, 처음으로 빙산 덩어리가 나뉘는 데 걸리는 최소 년수를 구하는 문제이다.

코드 리뷰

• 푸는 시간을 줄이는 것에 신경쓰다보니 코드 질이 굉장히 안좋은 것 같다.
• 푸는 시간은 줄였지만, 코드는 다음에 다시 예쁘게 짜봐야겠다.
• 일단 처음 보드배열 입력을 받을 때, 큐에 빙산들을 다 푸쉬했다. 이 때, cnt 0도 같이 푸쉬한다. 시간을 담는 변수이다.
• icebreak 함수에 들어가서, 빙산 주변 바다에 맞춰 빙산의 변한 높이를 저장하고, 큐에 그 좌표를 새로 푸쉬한다. 이 땐 cnt+1이 같이 푸쉬된다. 1년이 지났다는 뜻이다.
• 큐에서 값을 뽑을 때, 기존의 cnt값과 큐 front 값이 다른 경우에 1년이 지났다는 뜻이므로 함수를 탈출한다.
• 이 때, 중요한 것은 빙산이 녹아서 0이된것과 원래 바다였던 것을 check 배열을 통해 구분한다. 1년이 지나면, 그때 빙산이 녹아 0이된 부분을 check배열을 통해 바다로 바꿔준다. (check값이 0인 경우 바다, 1인 경우 육지)
• 1년이 지나면 bfs 탐색을 하여 빙산이 한번에 탐색이 되는지 확인한다. 한번에 탐색이 안되는 경우 년도를 출력해주고, 한번에 탐색이 되는 경우는 다시 위의 상황을 반복시켜준다. 이미 큐에는 새로운 년도에 대한 값들이 푸쉬 되어 있다.

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

typedef struct {
	int n;
	int m;
	int year;
}ice;

int N, M;
int board[300][300];
int check[300][300];
int landcheck[300][300];
int dc[4] = { 0,0,-1,1 };
int dr[4] = { -1,1,0,0 };
queue <ice> q;
queue <pair <int,int>> landq;
queue <pair <int, int>> checkq;

void icebreak() {
	int year = q.front().year;
	while (!q.empty()) {
		int n = q.front().n;
		int m = q.front().m;
		int cnt = q.front().year;
		int breakcnt = 0;
		if (cnt != year) break;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nnext = n + dc[k];
			int mnext = m + dr[k];
			if (nnext<0 || nnext>N || mnext<0 || mnext>M) continue;
			else if(board[nnext][mnext]==0 && check[nnext][mnext]==0){
				breakcnt++;
			} 
		}
		board[n][m] -= breakcnt;
		if (board[n][m] < 0) board[n][m] = 0;
		if (board[n][m] == 0) checkq.push(make_pair(n, m));
		q.push({ n,m,cnt + 1 });
	}
}

void bfs(int n, int m, int cnt) {
	landq.push({n,m});
	landcheck[n][m] = 1;
	while (!landq.empty()) {
		int n = landq.front().first;
		int m = landq.front().second;
		landq.pop();
		for (int k = 0; k < 4; k++) {
			int nnext = n + dc[k];
			int mnext = m + dr[k];
			if (nnext<0 || nnext>N || mnext<0 || mnext>M || landcheck[nnext][mnext] == 1) continue;
			else if (board[nnext][mnext] != 0 && landcheck[nnext][mnext]==0) {
				landq.push({ nnext, mnext});
				landcheck[nnext][mnext] = 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	int ans = 0;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			cin >> board[n][m];
			if (board[n][m] != 0) {
				q.push({ n,m,0 });
				check[n][m] = 1;
			}
		}
	}
	int landcnt = 0;
	int tmp = 0;
	int tmp2 = 0;
	while (1) {
		icebreak();
		while (!checkq.empty()) {
			check[checkq.front().first][checkq.front().second] = 0;
			checkq.pop();
		}
		tmp = 0;
		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (board[n][m] != 0) {
					tmp = 1;
					bfs(n,m,landcnt);
					break;
				}
			}
			if (tmp == 1) break;
		}
		tmp2 = 0;
		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (board[n][m] != 0 && landcheck[n][m]==0) {
					ans = q.front().year;
					tmp2 = 1;
					break;
				}
			}
			if (tmp2 != 0) break;
		}
		int tmp3 = 0;
		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (board[n][m] != 0) {
					tmp3 = 1;
					break;
				}
			}
			if (tmp3 == 1) break;
		}
		memset(landcheck, 0, sizeof(landcheck));
		if (tmp2 != 0) break;
		if (tmp3 == 1) continue;
		if (tmp3 == 0) {
			cout << '0' << '\n';
			return 0;
		}
	}
	cout << ans << '\n';
	return 0;
}