[백준 알고리즘] 2636번: 치즈
March 08, 2021
https://www.acmicpc.net/problem/2636
문제
문제
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
풀이
이전에 풀었던 토마토 문제와 비슷하다고 생각했는데, 동일한 방법으로는 풀 수 없었다. 이 문제에서는 구멍이 뚫려야지 치즈가 녹기 시작한다는 특수한 조건이 있다. 그래서 단순히 모든 치즈 영역을 탐색하거나 공기 영역을 탐색하는 것으로는 해결할 수 없다. 그래서 나는 시작점으로부터 모든 공기영역를 dfs로 한번에 탐색하는 것을 1시간으로 잡았다. 다른 공기 영역이 있더라도 한번에 그곳까지 탐색할 수 없다면 그래프 내에 존재하는 독립적인 트리이기 때문에 아직 공기가 통하지 않는 영역이다.
이때 공기가 접촉하게 되는 치즈영역(1)을 바로 공기영역(0)으로 바꿔주게 되면, 방금 공기로 바꾼 영역인데도 dfs가 탐색해버리고 만다. 그래서 나는 해당 시간에 녹게되는 치즈는 모두 정수 2로 바꾸어두고 남아있는 치즈개수를 세면서 0으로 바꿔주도록 했다.
한가지 놓치기 쉬운 부분이 탐색 시작위치의 초기화이다. 만약 일반 dfs 를 진행하는 것 처럼 시작지점을 순서대로 지정해서 방문되지 않은 노드를 확인하게 되면 다음과 같은 반례가 생긴다.
input :
3 3
1 1 1
1 1 1
1 1 0
output :
8
1마지막 0에 대한 탐색을 진행할 때, (2, 1) 과 (1, 2)에 있는 1이 0으로 바뀌게 되는데, 탐색 시작점을 단순히 2중 반복문으로 구성하면 마지막 0이 탐색의 마지막 지점이기 때문에 탐색이 곧바로 종료되어 버린다. 그래서 나는 한 dfs 가 끝났을 때, 탐색 시작점을 다시 (0, 0) 으로 하도록 했다.
코드
' '
#include <cstdio>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;
int board[101][101];
bool visited[101][101];
int N, M;
int countCheese(){
int cnt = 0;
for (int i = 0 ; i < N ; i++){
for (int j = 0 ; j < M ; j++){
if (board[i][j] == 1) cnt++;
if(board[i][j] == 2) board[i][j] = 0;
visited[i][j] = false;
}
}
return cnt;
}
bool isMovePossible(int row, int col){
return row >= 0 && row < N && col >=0 && col < M;
}
void dfs(int row, int col) {
visited[row][col] = true;
int rowDir [] = {0, 0, 1, -1};
int colDir [] = {1, -1, 0, 0};
for (int i = 0 ; i < 4 ; i++){
int nextRow = row + rowDir[i];
int nextCol = col + colDir[i];
if (isMovePossible(nextRow, nextCol) && !visited[nextRow][nextCol]){
if (board[nextRow][nextCol] == 1) board[nextRow][nextCol] = 2;
else if (board[nextRow][nextCol] == 0) {
dfs(nextRow, nextCol);
}
}
}
}
int main (){
int prevCheese;
int hrs = 0;
scanf("%d %d", &N, &M);
for (int i = 0 ; i < N ; i++){
for (int j = 0 ; j < M ; j++){
scanf("%d", &board[i][j]);
}
}
for (int i = 0 ; i < N ; i++){
for (int j = 0 ; j < M ; j++){
if (board[i][j] == 0 && !visited[i][j]){
hrs++;
prevCheese = countCheese();
dfs(i, j);
if(countCheese() == 0){
printf("%d\n%d", hrs, prevCheese);
exit(0);
}
i = j = 0;
}
}
}
}
