BaekJoon 2573 빙산

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

소스결과 2164 KB / 96 ms

출처 Baekjoon, KOI 2006 초등부 2번

언어 C++ 17

분류 BFS, DFS

 

설명

지구 온난화로 인하여 빙산이 녹아 내릴때 주어진 빙산이 녹아 2개 이상의 빙산으로 분리 될 때 까지 얼마만큼의 시간이 걸리는지 알아내는 문제

 

먼저, 빙산이 녹는 양은 0이 아닌 현재 위치를 기준으로 상하좌우 4방향의 값이 0인 즉 바닷물인 부분의 수 만큼 녹아 내린다.

또한 같은 시간에 녹아 내리는 양은 탐색 순서에 영향을 받지 않는다. ( (1,1)의 값이 0으로 줄었다고 해서 (1,2)의 값이 3이 줄어드는 것이 아닌 2가 줄어듦)

BFS나 DFS가 사용되는 부분은 빙산이 몇개로 이루어져 있는지 판단 될 때 사용된다.

빙산이 녹아 내리는 양에는 탐색이 필요 없다.

 

현재 빙하 덩어리의 수가 1일 때 녹아내리는 부분을 구현 하기만 하면 된다.

 

알고리즘

1. 빙하의 정보를 받아온다.

2. 현재 빙하 덩어리 수를 구하고 빙하 덩어리 수가 1인지 판별한다.

3. 현재 빙하의 수가 1이면 이번 해에 빙하를 녹이고, 녹은 빙하의 양이 0이 되지 않는 부분은 빙하 위치를 다시 저장한다.

4. 마지막으로 구해진 덩어리 수가 1보다 크면 빙하가 2덩어리 이상으로 나누어 진 경우이므로 녹아내리는 데 까지 걸린 해의 수를 출력한다.

5. 덩어리 수가 0이면 전부 녹아내렸으므로 0을 출력한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 300;
const short posX[4] = { 1, 0, -1, 0 };
const short posY[4] = { 0, 1, 0, -1 };
short board[MAX + 1][MAX + 1];

int n, m;

struct Ice {
	short x;
	short y;
	short val;

	Ice() : x(0), y(0), val(0) {};
	Ice(short x, short y, short v) : x(x), y(y), val(v) {};
};

int countIcePiece()
{
	queue<Ice> q;
	int ret = 0;

	bool check[MAX + 1][MAX + 1] = {};

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
		{
			if (!board[i][j] || check[i][j])
				continue;

			q.push(Ice(i, j, 0)); // 현재 위치를 저장
			check[i][j] = true; // 현재 위치를 방문한 것으로 판별

			while (!q.empty())
			{
				Ice cur = q.front();
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					short nextX = cur.x + posX[i];
					short nextY = cur.y + posY[i];

					if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m && board[nextX][nextY] && !check[nextX][nextY]) // 빙하인 부분을 Push
					{
						check[nextX][nextY] = true;
						q.push(Ice(nextX, nextY, 0));
					}
				}
			}
			++ret;
		}
	}

	return ret;
}

int main()
{
	queue<Ice> iceberg;
	queue<Ice> meltIce;
	int turn = 0;
	int piece = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
			if (board[i][j])
				iceberg.push(Ice(i, j, board[i][j]));
		}

	while ((piece = countIcePiece()) == 1) // 현재 빙하 덩어리 수를 구하고 저장한다.(빙하 덩어리 판별용)
	{
		while (!iceberg.empty())
		{
			Ice cur = iceberg.front();
			iceberg.pop();

			int count = 0;
			for (int i = 0; i < 4; i++)
			{
				short nextX = cur.x + posX[i];
				short nextY = cur.y + posY[i];

				if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m && !board[nextX][nextY]) // 바닷물인 부분의 수를 구한다.
					++count;
			}
			meltIce.push(Ice(cur.x, cur.y, count)); // 녹일 부분을 저장시킨다.
		}

		while (!meltIce.empty())
		{
			Ice cur = meltIce.front();
			meltIce.pop();

			if ((board[cur.x][cur.y] -= cur.val < board[cur.x][cur.y] ? cur.val : board[cur.x][cur.y])) // 녹을 값이 현재 값보다 크면 현재 값을 뺀다.
				iceberg.push(Ice(cur.x, cur.y, board[cur.x][cur.y])); // 빙하가 더 녹아내릴 수 있다면 다시 저장한다.
		}
		++turn; // 해 추가
	}

	if (piece > 1) // 두 덩어리 이상으로 분리 된 경우
		cout << turn;
	else // 전부 녹은 경우
		cout << 0;

	return 0;
}