(C++) [백준 2573번] 빙산

 

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

2573번: 빙산

 

BFS를 이용해서 푸는 문제이다.

이 문제는 (1) 빙산이 동시에 녹고, (2) 녹은 다음 시간이 흐르고 빙산이 나누어졌는지 확인해주어야 한다.

그래서 내가 생각한 방법은 다음과 같다.

 

1. 빙산을 동시에 녹인다.

2. 시간을 1년 더해준다.

3. 이후 BFS를 통해 빙산이 연결되어있는지 확인한 후, 연결되어있지 않거나 빙산이 1개 뿐이라면 시간을 리턴한다.

4. 만약 빙산이 연결되어있다면 1~3번을 빙산의 개수가 0개가 될 때 까지 반복한다.

 

 

#include <iostream>
#include <queue>
using namespace std;
#define MAX 302
#define X first
#define Y second
#define ICE 0
int board[MAX][MAX];
int iceBoard[MAX][MAX];
bool check[MAX][MAX];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m, bergCnt, cnt;
queue <pair<int, int>> q;
void input()
{
	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]) bergCnt++;
		}
	}
}
void init()
{
	for (int i = 0; i < n; i++)
	{
		fill(iceBoard[i], iceBoard[i] + MAX, 0);
		fill(check[i], check[i] + MAX, false);
	}
}
void melting()
{
	for (int i = 0; i < n; i++) // 빙산 주위에 0이 몇개 있는지 체크
	{
		for (int j = 0; j < m; j++)
		{
			int iceCnt = 0;
			if (board[i][j] == ICE) continue;
			q.push({ i,j });
			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 || ny < 0 || nx >= n || ny >= m) continue;
				if (board[nx][ny] == ICE) iceCnt++;
			}

			iceBoard[cur.X][cur.Y] += iceCnt;

		}
	}

	for (int i = 0; i < n; i++) // 체크한 개수만큼 녹이기
	{
		for (int j = 0; j < m; j++)
		{
			if (iceBoard[i][j] != 0)
			{
				board[i][j] -= iceBoard[i][j];
				if (board[i][j] <= 0)
				{
					board[i][j] = 0;
					bergCnt--;
				}
			}
		}
	}
}
void onePointBFS()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j]) // board[i][j]가 빙산이면
			{
				q.push({ i,j }); // 시작점 전부 넣기
				break;
			}
			if (q.size() != 0) break;
		}
	}
	while (!q.empty()) // 시작점 1개로 고정하고 돌려서 이어져있는지 확인
	{
		auto cur = q.front(); q.pop();
		check[cur.X][cur.Y] = true;
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (check[nx][ny] || !board[nx][ny]) continue;
			check[nx][ny] = true;
			q.push({ nx,ny });
		}

	}
}
bool checking()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] && !check[i][j]) return true; // 빙산이 있는데 BFS로 방문하지 못한 경우 
														// = 빙산이 나눠진 경우
		}
	}
	return false;
}
int solve()
{
	while (bergCnt != 0)
	{
		melting();
		cnt++; // 1초 증가

		if (bergCnt == 1) return cnt; // 빙산 개수가 1개면 종료
		onePointBFS();
		if (checking()) return cnt;
		init();
	}
	return 0;
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	input(); cout << solve();
}

 

melting() 함수에서 먼저 각 빙산마다 주위에 얼음이 몇개인지 체크만 하고,  iceBoard라는 배열에 저장해둔 다음

반복문이 한번 끝나면 새 반복문을 통해서 iceBoard의 값만큼 빼준다. 이렇게 하지 않으면 동시에 빙산을 녹일 수가 없다.

 

이후 시간을 1년 증가시키고, 빙산 개수가 만약 1개라면 종료한다.

onePointBFS()를 통해 임의의 1개 점을 찾고 그 점으로 BFS를 돌려서 빙산이 모두 연결되어있는지 확인한다.

이후 checking()을 통해 연결되어있는지 아닌지 확인하고, 만약 연결되어있지 않다면 년을 리턴하고 종료한다.

 

만약 반복문을 빠져나온다면 다 녹아버린 상태이므로 0을 리턴하면 된다.