[백준 2638] 치즈 (C++)

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

문제

---

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

 

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

 

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

출력

---

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

문제 풀이

---

그래프 탐색 문제.

이 문제의 핵심은 내부 공기와 외부 공기를 구분하는 것이다. 치즈의 일부분이 외부 공기와 2면 이상 접촉했다면 해당 부분이 사라진다.

모눈 종이의 모서리 부분은 치즈가 놓이지 않으므로, 이 부분은 무조건 외부 공기이다. 해당 위치를 기준으로 bfs 탐색이나. dfs 탐색을 진행해주면 내부 공기가 있는 부분는 치즈에 의해 접근할 수 없게 된다. 따라서 탐색이 끝나면 외부 공기(해당 칸이 0이면서 방문함), 내부 공기(해당 칸이 0로 표시되면서 방문하지 않음), 치즈(해당 칸이 1로 표시됨)으로 나누어진다.

치즈의 모든 부분을 탐색하며 인접한 4칸 중 '0이면서 방문한 칸'이 2 칸 이상인지를 확인하고 해당 칸을 0으로 표시한다. 다음 칸을 탐색할 때 0으로 표시한 것이 영향을 주지 않도록 1시간 후의 배열은 따로 배열을 만들어 저장해둔다.

외부 공기 탐색 -> 치즈 탐색하며 1시간 후의 치즈 상태 저장 -> 방문 상태 초기화를 모든 치즈가 사라질 때까지 반복하면 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

queue<pair<int, int>> bfsQueue;
int** map;
int** nextTimeMap;
bool** isVisited;
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
int N, M;

void bfs(int startX, int startY)
{
	bfsQueue.push(pair(startX, startY));
	while (!bfsQueue.empty())
	{
		pair<int, int> currentFront = bfsQueue.front();
		for (int i = 0; i < 4; i++)
		{
			int nextX = currentFront.first + dx[i];
			int nextY = currentFront.second + dy[i];
			if (nextX >= 0 && nextX < N&& nextY>=0 && nextY < M && isVisited[nextX][nextY]==false&& map[nextX][nextY]==0)
			{
				isVisited[nextX][nextY] = true;
				bfsQueue.push(pair(nextX, nextY));
			}
		}
		bfsQueue.pop();
	}
}

bool check(int x, int y)
{
	int count = 0;
	for (int i = 0; i < 4; i++)
	{
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY] == true)
		{
			count++;
		}
	}
	if (count >= 2)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void copyNextTimeMap()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			isVisited[i][j] = false;
			map[i][j] = nextTimeMap[i][j];
		}
	}
}

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

	cin >> N >> M;
	map = new int*[N];
	nextTimeMap = new int*[N];
	isVisited = new bool*[N];
	for (int i = 0; i < N; i++)
	{
		map[i] = new int[M];
		nextTimeMap[i] = new int[M];
		isVisited[i] = new bool[M];
		for (int j = 0; j < M; j++)
		{
			cin>>map[i][j];
			nextTimeMap[i][j] = 0;
			isVisited[i][j] = false;
		}
	}

	int time = 0;
	bool isChanged = false;
	while (true)
	{
		isChanged = false;
		bfs(0, 0);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (map[i][j] == 1)
				{
					isChanged = true;
					if (check(i, j) == true)
					{
						nextTimeMap[i][j] = 0;
					}
					else
					{
						nextTimeMap[i][j] = 1;
					}
				}
				else
				{
					nextTimeMap[i][j] = 0;
				}
			}
		}
		if (isChanged == false)
		{
			break;
		}
		else
		{
			time++;
			copyNextTimeMap();
		}
	}
	cout << time << "\n";
	return 0;
}