백준 2573번: 빙산 (C++)

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

2573번: 빙산

 

floodfill을 통해서 빙산이 두 개가 될 때까지 빙산이 녹는 과정을 구현하면 된다. 

 

빙산이 녹는 것을 구현할 때 주의할 사항은, 녹아서 0이 된 빙산을 같은 해야 원래 녹아있던 것으로 보지 않는 것이다.

 

이는 방문 처리 배열을 통해서 처리해주면 된다. 녹아서 바다가 되버린 빙산이라도, 방문처리가 되어있기 때문에, 방문 처리가 되지 않은 바다만 빙산을 녹이는 데에 영향을 끼칠 수 있게 구현을 하면 된다.

 

또 유의할 것은 방문처리 배열의 초기화이다. 빙산을 녹이는 과정과, 빙산의 개수를 파악하기 위해서 floodfill을 하는 과정은 모두 방문처리 배열을 이용한다. 이때 한 번 방문처리 배열을 사용했으면, 바로 초기화를 해줘야 한다.

 

#include<iostream>
using namespace std;
int R, C, m[300][300];
bool vis[300][300];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int row, int col) {
	vis[row][col] = true;
	
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		
		if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
		if (vis[nr][nc] || m[nr][nc] == 0) continue;
		dfs(nr, nc);
	}
}
int Flood() {
	int res = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (m[i][j] != 0 && !vis[i][j]) {
				res++;
				if (res > 1) break;
				dfs(i, j);
			}
		}
	}
	return res;
}
void init() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			vis[i][j] = false;
		}
	}
}
void Melt(int row, int col) {
	vis[row][col] = true;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (nr < 0 || nc < 0 || nr >= R || nc >= C || vis[nr][nc]) continue;
		if (m[nr][nc] == 0) cnt++;
		else if (m[nr][nc] == 1) Melt(nr, nc);
	}
	if (m[row][col] - cnt <= 0) m[row][col] = 0;
	else
		m[row][col] = m[row][col] - cnt;
}

int main() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> m[i][j];
		}
	}

	int year = 0;
	while (1) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (m[i][j] != 0 && !vis[i][j]) {
					Melt(i, j);
				}
			}
		}
		year++;
		init();
		if (Flood() > 1) {
			cout << year << '\n';
			break;
		}
		init();
		if (Flood() == 0) {
			cout << 0 << '\n';
			break;
		}
		init();
	}
	return 0;
}