BOJ 백준 2573 빙산

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

2573번: 빙산

 

문제 풀이)

 

    입력을 받을 때 총 빙산의 개수와 빙산의 위치를 저장해주고, vector에 빙산의 구조체를 넣어준다.

 

    구조체에는 빙산의 좌표 x, y의 int형 2개와 녹았는 지 아닌 지를 체크할 bool형 변수가 있다.

    

    첫 번째 단계에서는 대륙이 나누어져 있는 지 체크해준다.

 

        vector에 녹지 않은 빙산 첫 번째 요소를 찾아내어 BFS를 돌려준다. BFS를 돌면서 탐색한 빙산의 개수를

 

        현재 남아있는 빙산의 개수와 비교해주면서 만약 개수가 다를 시 걸린 시간 (while문 루프 횟수 ) 를

 

        출력해준다. BFS를 돌면서 탐색한 빙산 하나하나 마다 얼마가 녹아야 하는 지 체크할 이차원 배열을

 

        만들어 값을 넣어준다.

 

 

    두 번째 단계에서는 첫 번째 단계에서 얼음이 얼마나 녹았는 지 계산한 배열을 실제 맵에 적용한다.

 

    얼음이 녹은 경우가 있다면 빙산의 개수를 1 감소해주면 된다. 만약 빙산의 개수가 0이 되었다면

 

    대륙이 나누어지기 전에 다 녹아버린 것이므로 0을 출력해주면서 끝내주면 된다.

 

 

 

 

 

소스 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <list>

using namespace std;

typedef struct _tagNode
{
	int x;
	int y;
	bool bMelt;

}NODE, *PNODE;

const int SIZE = 310;
int r, c, vSize;
int map[SIZE][SIZE] = { 0 };
int aMinus[SIZE][SIZE] = { 0 };
int xDir[4] = { 1,-1,0,0 };
int yDir[4] = { 0,0,1,-1 };

int nIceberg = 0;
bool bClear = false;

vector<NODE> v;

void CheckDivision()
{
	bool visit[SIZE][SIZE] = { 0 };
	int nNum = 0;

	queue<NODE> q;
	for (int i = 0; i < vSize; ++i)
	{
		if (!v[i].bMelt)
		{
			q.push({ v[i].x, v[i].y });
			visit[v[i].x][v[i].y] = true;
			break;
		}
	}
	
	while (!q.empty())
	{
		int qSize = q.size();
		for (int i = 0; i < qSize; ++i)
		{
			int cur_x = q.front().x;
			int cur_y = q.front().y;
			q.pop();
			nNum++;

			for (int j = 0; j < 4; ++j)
			{
				int next_x = cur_x + xDir[j];
				int next_y = cur_y + yDir[j];
				
				if (next_x < 0 || next_y < 0 ||
					next_x >= r || next_y >= c)
					continue;
				if (map[next_x][next_y] == 0)
				{
					aMinus[cur_x][cur_y]++;
				}
			}

			for (int j = 0; j < 4; ++j)
			{
				int next_x = cur_x + xDir[j];
				int next_y = cur_y + yDir[j];

				if (next_x < 0 || next_y < 0 ||
					next_x >= r || next_y >= c)
					continue;
				if (visit[next_x][next_y]) continue;
				if (map[next_x][next_y] == 0) continue;

				q.push({ next_x, next_y });
				visit[next_x][next_y] = true;
			}
		}
	}

	if (nNum != nIceberg) bClear = true;

	return;
}

void MeltIceberg()
{
	for (int i = 0; i < vSize; ++i)
	{
		if (!v[i].bMelt)
		{
			if (map[v[i].x][v[i].y] - aMinus[v[i].x][v[i].y] <= 0)
			{
				nIceberg--;
				map[v[i].x][v[i].y] = 0;
				v[i].bMelt = true;
			}
			else
				map[v[i].x][v[i].y] -= aMinus[v[i].x][v[i].y];

			aMinus[v[i].x][v[i].y] = 0;
		}
	}
}

int main()
{
	
	scanf("%d %d", &r, &c);
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j])
			{
				v.push_back({ i, j, false });
				++nIceberg;                                       
			}
		}
	}
	vSize = v.size();
	int nDay = 0;

	while (!bClear)
	{
		// 대륙 체크
		CheckDivision();
		if (bClear) break;
		nDay++;

		// 얼음 녹기
		MeltIceberg();
		if (nIceberg <= 0)
		{
			puts("0");
			return 0;
		}
	}
	printf("%d\n", nDay);

	return 0;
}