[BOJ] 2573:빙산

 

 

0. 문제

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

2573번: 빙산

 

1. 문제분석

-  한 칸(노드)에서 시작해서 상하좌우로 인접한 칸을 연속해서 탐색한다는 점에서 DFS 또는 BFS 알고리즘을 사용해 문제를 풀어야 함을 알 수 있다. 별다르게 최단경로를 파악할 필요는 없으므로, DFS나 BFS 둘 다 크게 상관 없을 듯 하지만, 이번에는 DFS를 사용했다.

 

2. 주의할 점

- 문제를 성급히 읽으면 단순히 빙산이 다 녹을때까지의 연수만 계산하는 알고리즘을 짜게된다. 하지만 구해야 하는 것은 "두 덩어리 이상으로 분리되는 최초의 시간"임을 명심하자.

- 단순히 칸 별 값이 0일 때 dfs를 call 하지 않는 것 만으로는 부족하다. 왜냐하면 dfs 함수를 진행하면서, 원래는 빙산이 다 녹지 않았지만(값이 0이 아니었지만), 해당 연도 도중에 0값이 되어버리는 칸도 있기 때문이다. 따라서 방문배열(vtd)를 별도로 사용해준다. 

 

3. 소스코드(C++)

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#define endl '\n'
#define INF 987654321
using namespace std;
typedef pair<int, int> ii;

int n, m, cnt;
int grid[301][301];
bool vtd[301][301];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };

void dfs(int y, int x) {
	vtd[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		if (vtd[ny][nx]) continue;
		if (grid[ny][nx] == 0) grid[y][x] = max(0, grid[y][x] - 1);
		else dfs(ny, nx);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int ans = -1;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> grid[i][j];
		}
	}

	while (true) {
		cnt = 0;
		ans++;
		memset(vtd, false, sizeof(vtd));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (grid[i][j] == 0 || vtd[i][j]) continue;
				dfs(i, j);
				cnt++;
			}
		}
		if (cnt != 1) break;
	}

	if (cnt == 0) cout << 0;
	else cout << ans;
	return 0;
}

 

4. 여담

- dfs를 통해서 연결된 집단 개수를 파악한다는 점에서 boj2667 단지번호붙이기와 문제 풀이 방식이 비슷하다.

- 또한 상하좌우에 위치한 노드 값에 따라 현재 위치 값이 변화한다는 점에서 boj2636 치즈와도 문제 풀이 방식이 비슷하다.