[백준 2573] 빙산

문제 풀이

 

문제를 읽고 아래와 같이 요약을 했다.

1. 빙산을 언제까지 녹일 수 있을까?

2. 빙산을 어떻게 녹일까?

3. 언제 빙산이 2덩어리 이상으로 나누어질까?

 

1번부터 보자.

빙산을 언제까지 녹일 수 있을까?

빙산이 2차원 배열에서의 높이가 모두 0이 되어버리면 빙산은 다 녹았다고 판단할 수 있다.

간단하게 말해서 하나라도 0보다 큰 숫자(높이)가 있다면 아직 빙산이 다 녹지 않은 것이다.

 

2번을 보자.

빙산을 어떻게 녹일까?

빙산은 녹을 때 자신의 위치에서 상, 하, 좌, 우로 바닷물이 인접해있으면 그 수만큼 빙산의 높이를 줄이게 된다.

그런데 한 가지 주의할 점이 칸 마다 4방향을 확인하면서 녹이게 되면 안 된다.

A라는 칸에서 4방향 해서 녹인 빙산으로 갱신하면 그 다음 B라는 칸에서 A 라는 칸과 인접해있을 경우,

B 라는 칸도 영향을 받을 수 있기 때문이다.

 

빙산이라는 건, 한 번에 빙산 덩어리가 녹는 거지 개별적으로 녹는 것이 아니기 때문에,

녹이기 전의 빙산 구조와 녹인 후의 빙산 구조 2개를 저장할 수 있는 자료구조가 필요하다.

2개의 2차원 배열을 선언하면 해결할 수 있다.

 

3번을 보자.

언제 빙산이 2덩어리가 될까?

간단히 생각해서 아직 녹지 않은 빙산을 찾아서 그 빙산으로부터 4방향을 탐색하면서 방문을 한다.

즉, DFS를 돌린 수만큼이 결국 빙산의 덩어리 수다.

 

소스 코드

 

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

const int MAX = 301;
const int dx[] = { 0,0,-1,1 };
const int dy[] = { 1,-1,0,0 };

int N, M;
int board[MAX][MAX];     // 현재 빙산의 상태
int prevBoard[MAX][MAX]; // 기존의 빙산 기억
bool visit[MAX][MAX];

void input()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}
}

void dfs(int x, int y)
{
	visit[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (visit[nx][ny] == false && board[nx][ny] > 0)
		{
			dfs(nx, ny);
		}
	}
}

bool checkIce()
{
	//빙산이 2덩이이상으로 나눠지는지
	fill(visit[0], visit[0] + MAX * MAX, false);

	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (visit[i][j] == false && board[i][j] > 0)
			{
				dfs(i, j);
				cnt++;
			}
		}
	}

	return cnt >= 2;
}

bool isMelt()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] > 0)
				return false;
		}
	}
	return true;
}

void iceMelt()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			prevBoard[i][j] = board[i][j];

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (prevBoard[i][j] > 0)
			{
				// 자신을 기점으로 4방향의 바닷물을 체크한다.
				int cnt = 0;
				for (int d = 0; d < 4; d++)
				{
					int nx = i + dx[d];
					int ny = j + dy[d];
					if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
					if (prevBoard[nx][ny] == 0) cnt++;
				}

				// 인접한 바닷물 개수만큼 녹인다.
				board[i][j] -= cnt;
				if (board[i][j] < 0) board[i][j] = 0;
			}
		}
	}
}

void solve()
{
	input();

	int year = 0;
	while (isMelt() == false)
	{
		year++;

		iceMelt();

		if (checkIce() == true)
		{
			cout << year << endl;
			return;
		}
	}

	// 빙산이 녹을 때까지 나눠지지 않은 경우
	cout << "0\n";
}

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

	solve();
	return 0;
}