[BOJ] 2573 빙산 C++

문제 이해

n x m의 배열이 주어지고 한 덩이의 빙산으로 시작해서 두 덩이 이상으로 분리되는 최초의 시간을 구하는 문제.

단, 전부 다 녹을 때까지 두 덩이 이상으로 분리되지 않으면 0 출력.

 

 

 

 

 

아이디어 구상

2중 반복문 안에서 방문하지 않은 경우 bfs를 시작해서 빙산의 상하좌우를 탐색하여 0이면 2번 배열에 현 위치를

체크 해두고 양수라면 1번 배열에 방문체크를 하고 큐에 넣어준다. bfs 횟수는 곧 빙산의 덩어리의 개수를 의미한다.

 

 

 

 

코드

#include <stdio.h>
#include <algorithm>
using namespace std;
#define MX 305
int n, m, ice, sw;
int a[MX][MX], vis[MX][MX], vis2[MX][MX];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int inRange(int x, int y) {
	return 0 < x && x <= n && 0 < y && y <= m;
}

void bfs(int i, int j) {
	queue<pair<int, int>> q;
	q.push({ i,j });
	vis[i][j] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (inRange(nx, ny)) {
				if (a[nx][ny] <= 0) vis2[x][y]++;
				else {
					if (vis[nx][ny] == 0) {
						vis[nx][ny] = 1;
						q.push({ nx,ny });
					}
				}
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			if (a[i][j] > 0) ice++;
		}
	}
	int res = 0;
	while (1) {
		fill(vis[0], vis[MX], 0);
		fill(vis2[0], vis2[MX], 0);
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] > 0 && vis[i][j] == 0) { bfs(i, j); cnt++; }
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (vis2[i][j]) {
					a[i][j] -= vis2[i][j];
					if (a[i][j] <= 0) ice--;
				}
			}
		}
		res++;
		if (cnt > 1) { sw = 1; break; }
		if (ice == 0) break;
	}
	if (sw) printf("%d", res - 1);
	else printf("0");

	return 0;
}