[C/C++] 백준 - 2636번 : 치즈

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

2636번: 치즈

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

< 구해야 하는 것 >

- 치즈가 모두 녹아 없어지는데 걸리는 시간과, 없어지기 한 시간 전 남아있는 치즈의 개수

 

< 사용할 자료구조 및 알고리즘 판단 >

- 딱봐도 BFS를 사용해야 한다는 것을 알 수 있고, 그에 따라 Queue를 사용해야 한다.

단, 큐를 2개 사용할 것이다. 본인이 푼 과정을 풀이로 작성할테니 왜 큐를 2개 사용하는지는 거기서 살펴볼 것이다.

 

(1). 치즈의 가장자리로부터 치즈가 녹아 크기가 줄어든다. 이것에 대한 부분은 이미 문제에서 나와있으므로 따로 설명하지는 않겠다. 

(2). (1)로부터 치즈가 작아지며 모두 없어지는 시간과 없어지기 바로 직전 치즈의 개수는 반복문과 변수 초기화로 쉽게 해결할 수 있을 것이다, 그렇다면 이 문제에서 가장 까다로운 부분은 (1)에 해당되는 부분이다.

 

(1)을 어떻게 구현할 것인가, 나도 이 부분에서 10분정도 고민한 것 같다. 하던 방식대로 0과 1인 부분을 따로 생각해 

1부분에서 가장 자리를 판단해볼까 라고 생각했는데 문제 예제 그림1에서 오른쪽 맨위 사각형을 처리하는 부분이 쉽지 않을 것 같았다. 그리고 가장자리를 판단하는 코드를 작성하는 거에 자신이 없었다. 그래서 반대로 생각해보기로 했다.

 

1인 부분을 너비우선탐색을 하는 것이 아닌 0, 즉 비어있는 부분으로.  문제에서 가장자리는 모두 X표를 해놔서 이걸 이용해야겠다고 생각했다. 어처피 1,1은 비어있으니 이 좌표를 시작지점으로 해서, 비어있는 부분을 차례로 방문표시를 하며 지나가고 1인 부분이 나오면 또 다른 큐를 하나 만들어 그 좌표를 넣어주고 방문 표시를 해줬다. 여기서 또 다른 큐를 Erase큐로 칭하겠다. Erase큐에 넣는 이유는 같은 큐에 넣게 된다면 가장자리 치즈 뿐만 아니라 안쪽에 있는 치즈도 방문 큐에 넣기 때문이다. 그래서 Erase큐에 넣어 가장자리 치즈 개수만 파악해주는 것이다. 이거에 대한 함수를 하나 만들어주면 가장자리 치즈의 개수를 파악할 수 있다. 만약 가장자리 치즈 개수가 0이라면? 치즈가 존재하지 않는다는 것을 의미한다.

 

그리고 가장자리 치즈를 녹아없어지는 것은 Erase큐에 넣었던 좌표를 0으로 바꿔주는 것이다.

 

// input함수 : 입력에 해당하는 부분

// isEdgeCheese함수 : 녹아 없어질 가장자리 치즈를 Erase큐에 넣는 과정

// Count_Cheese함수 : 남아있는 치즈의 개수를 세는 함수

// Erase_Cheese함수 : isEdgeCheese함수에서 구한 녹아 없어질 가장자리 치즈를 녹아 없애는 부분을 나타낸 함수

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

// BOJ :: https://www.acmicpc.net/problem/2636

int adj[101][101];
bool visited[101][101];
int N, M, Time, Cnt;
queue<pair<int, int>> q;
queue<pair<int, int>> Erase;

const int dy[] = { 1,-1,0,0 };
const int dx[] = { 0,0,1,-1 };

void input() {
	cin >> N >> M;
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= M; x++) {
			cin >> adj[y][x];
		}
	}
}

void isEdgeCheese(int y, int x) {
	q.push(make_pair(y, x));
	visited[y][x] = true;

	while (!q.empty()) {
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = curY + dy[i];
			int nextX = curX + dx[i];

			if (nextY < 1 || nextX < 1 || nextY > N || nextX > M) continue;
			if (!visited[nextY][nextX] && !adj[nextY][nextX]) {
				q.push(make_pair(nextY, nextX));
				visited[nextY][nextX] = true;
			}
			else if (!visited[nextY][nextX] && adj[nextY][nextX]) {
				Erase.push(make_pair(nextY, nextX));
				visited[nextY][nextX] = true;
			}
		}
	}
}

int Count_Cheese() {
	int Count = 0;
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= M; x++) {
			if (adj[y][x]) Count++;
		}
	}
	return Count;
}

void Erase_Cheese() {
	while (!Erase.empty()) {
		int y_ = Erase.front().first;
		int x_ = Erase.front().second;
		Erase.pop();
		adj[y_][x_] = 0;
	}
}

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

	input();

	int Answer = INF;
	while (1) {
		memset(visited, false, sizeof(visited));
		isEdgeCheese(1, 1);
		if (!Erase.size()) break;
		Answer = min(Answer, Count_Cheese());
		Erase_Cheese();
		Cnt++;
	}
	cout << Cnt << endl;
	cout << Answer << endl;

	return 0;
}