[백준 2636번] 치즈

[백준 2636번] 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

 

 

 문제

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

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

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

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

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

 

 입력

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

 

 출력

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

 

 

 풀이

#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, int>> qu;
int N, M;
int arr[100][100];
int cnt[100][100];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void find0(int z, int x){
	queue<pair<int, int>> q0;
	q0.push(make_pair(z, x));
	qu.push(make_pair(z, x));
	while(!q0.empty()){
		int a = q0.front().first;
		int b = q0.front().second;
		q0.pop();
		for(int i=0;i<4;i++){
			int q = a + dx[i];
			int w = b + dy[i];
			if(q >= N || q < 0 || w >= M || w < 0) continue;
			if(arr[q][w] == 0){
				arr[q][w] = -1;
				cnt[q][w] = cnt[a][b];
				q0.push(make_pair(q, w));
				qu.push(make_pair(q, w));
			}
		}
	}
}

void ff(){
	while(!qu.empty()){
		int a = qu.front().first;
		int b = qu.front().second;
		qu.pop();
		
		for(int i=0;i<4;i++){
			int q = a + dx[i];
			int w = b + dy[i];
			if(q >= N || q < 0 || w >= M || w < 0) continue;
			
			if(arr[q][w] == 1){
				arr[q][w] = -2;
				cnt[q][w] = cnt[a][b] + 1;

				find0(q, w);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;
	
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin >> arr[i][j];
		}
	}
	
	find0(0, 0);
	ff();
	
	int r[100] = {0,};
	int t = 0;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(arr[i][j]!=-1){
				r[cnt[i][j]]++;
				if(t < cnt[i][j]) t = cnt[i][j];
			}
		}
	}
	
	cout << t << '\n' << r[t];
	return 0;
}

 매번 푸는 BFS문제와 접근이 조금 달라서 재밌었던 문제이다. 자주 풀던 문제가 하나에서 여러개로 퍼져나가는 느낌이라면 이 문제는 여러개에서 하나로 줄여나가는 느낌이다. 일단 가장자리는 치즈가 놓이지 않기 때문에 가장자리의 한 점으로 부터 치즈가 놓이지 않은 0인 부분을 bfs로 찾아서 큐에 넣는다. 다 찾았으면 큐에 있는 원소들로 원래 문제 풀듯이 bfs하면 되는데 치즈사이에 공간이 있는 경우가 그나마 까다로웠다. 처음 구현했던 방법으로는 치즈 사이 공간이 큐에 늦게 들어가서 잘못된 답이 나왔다. 치즈인 부분에 대한 값을 큐에 넣을 때, 빈 부분을 찾는 걸 같이 해주면서 해결했다.

 한국정보올림피아드 초등부 문제인데 초등학생이 이걸 푼다는게 믿기지가 않는다. 요즘 학원에서 예비고1 두명을 대상으로 수업을 해주면서 느낀바 때문인지 더 그런것 같다.