[백준 2573] 빙산

문제 링크 => 2573번: 빙산 (acmicpc.net)

2573번: 빙산

 

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

 

무난한 DFS 문제이다.

해당 문제에 대한 접근법은 다음과 같다.

 

ⓞ 시간을 1 증가시킨다. (count++)

 

① 빙산이 있는 지점(x, y)을 확인하여(X[x][y] != 0) 주변에 있는(동서남북) 바다의 갯수를 카운팅 한다.

     (카운팅한 값을 Y[x][y] 이라고 하자)

 

 

② 빙산이 있는 지점(x, y)을 확인하여 카운팅한 값을 빼서 빙산을 녹이도록 한다.

     (이때 음수가 되는 경우 0으로 처리)

 

③ dfs 를 이용하여 3가지 케이스를 고려한다.

      (1) 빙산이 하나로 묶이면 ⓞ 으로 돌아간다.

      (2) 빙산이 두개 이상으로 묶이면 지나온 시간(count)를 반환하도록 한다.

      (3) 빙산이 묶이지 않을 경우 즉, 없는 경우 0을 반환하도록 한다.

 

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>

using namespace std;

int row, col;
int X[301][301], Y[301][301];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool visited[301][301];

void init()
{
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			Y[i][j] = 0, visited[i][j] = false;
}

void dfs(int x, int y) 
{
	if (visited[x][y]) return;
	visited[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col && X[nextX][nextY])
			dfs(nextX, nextY);
	}
}

int solution() 
{
	int count = 0;
	while (++count) {
		init();
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (X[i][j]) {
					for (int k = 0; k < 4; k++) {
						int nextX = i + dx[k];
						int nextY = j + dy[k];
						if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col) {
							if (X[nextX][nextY] == 0) Y[i][j]++;
						}
					}
				}
			}
		}

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				X[i][j] -= Y[i][j];
				if (X[i][j] < 0) X[i][j] = 0;
			}
		}

		int op = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (X[i][j] && !visited[i][j]) {
					dfs(i, j);
					op++;
				}
				if (op > 1) return count;
			}
		}
		if (op == 0) return 0;
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> row >> col;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			cin >> X[i][j];
	cout << solution();

	return 0;
}