[백준/C++] 2573 빙산

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

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
#define MAX 301
int n, m;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
vector<vector<int>> arr;
vector<vector<int>> tmp;
vector<vector<bool>> visit;

void melting() {
	tmp = arr;

	for (int i = 0, x, y, cnt; i < n; i++)
	{
		for (int j = 0; j < m; j++) {
			if (arr[i][j] > 0) {
				cnt = 0;
				for (int k = 0; k < 4; k++) {
					x = i + dx[k];
					y = j + dy[k];

					if (x >= 0 && x < n && y >= 0 && y < m && !arr[x][y])
						cnt++;
				}
				tmp[i][j] -= cnt;
				tmp[i][j] = max(0, tmp[i][j]);
			}
		}
	}
	arr = tmp;
}

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y});
	visit[x][y] = true;

	while (!q.empty()) {
		int nx = q.front().first;
		int ny = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < n && gy >= 0 && gy < m && !visit[gx][gy] && arr[gx][gy]) {
				visit[gx][gy] = true;
				q.push({ gx, gy });
			}
		}
	}
}

int main() {
	FASTIO;
	int ans = 0, cnt;
	cin >> n >> m;
	arr.resize(n, vector<int>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	while (true) {
		cnt = 0;
		visit = vector<vector<bool>>(n, vector<bool>(m, false));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] && !visit[i][j]) {
					bfs(i, j);
					cnt++; 
				}
			}
		}

		if (cnt > 1) {
			cout << ans;
			break;
		}
		else if (cnt == 0)
		{
			cout << 0;
			break;
		}

		melting();
		ans++;
	}
	
	return 0;
}

설명

메인함수에서 빙산 정보를 입력받아 저장한다. 이후 while문에서 매번 빙산의 덩어리 개수를 구한다. 이를 위해 bfs를 이용한다. (방문하지 않은 좌표에 대해서 1 이상의 값이 저장되어 있다면 빙산이 존재하는 것이므로 해당 좌표에서 bfs를 돌리고 cnt를 1씩 증가시킨다. 최종적으로 cnt에 현재 상황에서의 빙산의 덩어리 개수를 저장하게 된다.) 덩어리 개수가 1 초과라면 빙산이 두 덩어리 이상으로 분리되었다는 의미이므로 ans를 출력하고 while문을 탈출한다.  만약 덩어리 개수가 0이라면 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않았다는 의미이므로 0을 출력하고 while문을 탈출한다. 

 

위의 경우에 해당하지 않는다면 하나의 덩어리 빙산이 존재한다는 의미이므로 빙산을 녹인다. 이때 녹는 상황을 melting 함수에서 구현한다. tmp에는 최종적으로 변화하게 될 빙산 정보를 저장할 것이다. 배열의 좌표 값이 1 이상이라면 동서남북으로 인접한 0의 개수를 센다. tmp[i][j]에서 앞에서 구한 개수를 빼주면 1년 뒤의 빙산의 높이가 된다. (빙산의 높이는 0 이상이어야 하므로 매번 0 이상이 될 수 있도록 한다.) arr에 tmp를 대입해서 최종 결과를 반영한다. 이후 ans를 1씩 증가시킨다.

 

느낀 점

시간초과나 메모리초과가 날 것을 염두하면서 나이브하게 코드를 짰는데 바로 통과했다...