[BOJ] 백준 2573번 빙산 C++

문제

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

2573번: 빙산

풀이

이 문제는 치즈 문제와 다르게 내부 공기/외부 공기의 구분이 없고, 영역의 개수를 구해야하기 때문에 모든 좌표에 대해 BFS를 돌아줘야한다.

board의 값이 0인(바다)인 곳에 대해 모두 탐색을 하여 빙산이 있는 곳을 만나면 빙산의 높이를 하나씩 감소시켜주었고, 빙산의 높이가 0이 되면 방문처리를 해주어 이번 탐색에 녹아버린 좌표에 대해서는 BFS를 막아주고 최종적으로 현재 영역의 개수를 리턴해주었다.

그렇게 while문을 돌며 리턴 받은 영역의 개수가 2를 넘으면 최소의 시간을 출력하고 프로그램을 종료한다.

2보다 작으면 현재 상태가 빙산을 녹일 수 있는 상태인지 판별해주어 녹일 수 있으면 while문을 계속 돌고, 녹일 수 없다면 0을 출력해주고 프로그램을 종료해주었다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;

int n, m;
int year = 0;
int area = 0;
int board[301][301];
bool visited[301][301];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int bfs()
{
	queue<pair<int, int>> q;

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

			q.push({ i,j });
			visited[i][j] = true;

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

				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.x + dx[dir];
					int ny = cur.y + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					{
						continue;
					}
					else
					{
						if (board[nx][ny] == 0 && !visited[nx][ny])
						{
							q.push({ nx,ny });
							visited[nx][ny] = true;
						}
						if (board[nx][ny] > 0)
						{
							board[nx][ny] -= 1;
							if (board[nx][ny] == 0)
							{
								visited[nx][ny] = true;
							}
						}
					}
				}
			}
		}
	}

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			visited[i][j] = false;
		}
	}

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

			area++;
			q.push({ i,j });
			visited[i][j] = true;

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

				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.x + dx[dir];
					int ny = cur.y + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					{
						continue;
					}
					if (visited[nx][ny] || board[nx][ny] == 0)
					{
						continue;
					}

					q.push({ nx, ny });
					visited[nx][ny] = true;
				}
			}
		}
	}

	return area;
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}

	while (true)
	{
		area = 0;
		bool canMelt = false;
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= m; j++)
			{
				visited[i][j] = false;
			}
		}

		year++;
		if (bfs() >= 2)
		{
			cout << year;
			break;
		}
		else
		{
			for (int i = 0; i <= n; i++)
			{
				for (int j = 0; j <= m; j++)
				{
					if (board[i][j] > 0)
					{
						canMelt = true;
					}
				}
			}

			if (canMelt)
			{
				continue;
			}
			else
			{
				cout << 0;
				return 0;
			}
		}
	}
}