BaekJoon 2573번: 빙산(C++) + 문제 오류

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

2573번: 빙산

문제의 예제인 그림 3번에 오류를 발견했다.

그림 3은 다음과 같이 설명되어 있으나 정확한 정답으로는

 

0 0 0 0 0 0 0

0 0 0 3 0 0 0

0 0 0 0 4 0 0 

0 0 3 2 0 0 0

0 0 0 0 0 0 0

 

위의 정답과 같은 세 덩이의 배열이 되어야 한다.

 

풀이법

1) while 반복을 통해, 덩이의 차이 없이 완전히 녹은 경우를 파악하여 0을 출력해야 한다. (allMelt 함수)

2) 매 반복시 visited 배열을 초기화 하여 bfs 활용시에 문제가 없도록 해야 한다.

3) arr배열에서 값이 있는 값을 bfs배열로 확인하여 덩이가 몇개로 떨어지는 지 확인해야 한다.

4) bfs 내에서는 인접한 배열을 확인하여 visited 배열에 방문한 값들을 true로 넣는다.

5) 한 덩이로 나올 경우 기존의 arr 배열을 문제에서 말한 대로 0과 접해있는 갯수만큼 값을 차감 시킨다. (이 때 새로운 배열을 만들지 않고 arr배열 하나로 값을 수정 시에, 이전에 수정한 값에 의하여 이상한 값이 나올 수 있으므로 새로운 배열 arr2를 만드는 것을 추천한다.)

 

 

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

int n, m;
int arr[301][301];
int arr2[301][301];
bool visited[301][301];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int cnt = 0;
void clearVisited()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visited[i][j] = false;
}
void bfs(int a,int b)
{
	queue<pair<int, int>> q;
	visited[a][b] = true;
	q.push({ a,b });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 1 || nextY < 1 || nextX >= n - 1 || nextY >= m - 1)
				continue;
			if (arr[nextX][nextY] > 0 && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,nextY });
			}
		}
	}
}
void changeArr()
{
	for (int i = 1; i < n - 1; i++)
	{
		for (int j = 1; j < m - 1; j++)
		{
			if (arr[i][j] > 0)
			{
				int cntTemp = 0;
				for (int k = 0; k < 4; k++)
				{
					int nextX = i + vx[k];
					int nextY = j + vy[k];
					if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
						continue;
					if (arr[nextX][nextY] == 0)
						cntTemp++;
				}
				arr2[i][j] = arr[i][j] - cntTemp;
				if (arr2[i][j] < 0)
					arr2[i][j] = 0;
			}
		}
	}
	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < m - 1; j++)
			arr[i][j] = arr2[i][j];
}
bool allMelt()
{
	bool check = true;
	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < m - 1; j++)
			if (arr[i][j] != 0)
				check = false;
	return check;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	while (1)
	{
		bool check = false;
		check = allMelt();
		if (check == true)
		{
			cout << 0;
			break;
		}
		clearVisited();
		int res = 0;
		for (int i = 1; i < n - 1; i++)
			for (int j = 1; j < m - 1; j++)
				if (arr[i][j] > 0 && !visited[i][j])
				{
					bfs(i,j);
					res++;
				}
		
		if (res == 1)
		{
			cnt++;
			changeArr();
		}
		else
		{
			cout << cnt;
			break;
		}
	}
}