백준 2638 치즈 C++ [골드3]

문제

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

<그림 1>

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

<그림 2>

<그림 3>

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

입력

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

출력

 

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

 

 

 

문제풀이

처음 문제를 꼼꼼히 읽지 않아 많이 해맸다. "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다"라는 조건이 있는 것을 보지 못한 것이다. 이 조건이 없을 경우, 치즈가 길게 늘어져 있어 빈 공간을 두 개, 혹은 그 이상으로 나누게 될 경우 0으로 되어 있는 빈 공간이 치즈로 싸여있는지, 정말 외곽인지 판단하는 과정이 조금 더 복잡해진다.

어쨌든 이 문제에선 가장자리엔 치즈가 없으므로, BFS를 이용해 0,0부터 시작해 빈 공간을 찾아내어 체크를 해주면 된다.

 

그럼 우선 절차적으로 풀이 과정에 대해 알아보자.

1. 빈 공간이 치즈 내부에 있는지 외부에 있는지 확인한다. -> 외부에 있을 경우 0에서 2로 변환

2. 치즈가 외부에 2칸 이상 닿아있는지 확인

3. 2칸이상 닿아있는 치즈 삭제

4. 치즈가 삭제되면서 생긴 공간을 확인한다. 치즈가 삭제되면서 외부 공간과 내부 공간이 이어졌는지 확인한다. (1번을 다시 반복하면 됨)

2~4 반복

 

1. 빈 공간이 치즈 내부에 있는지 외부에 있는지 확인한다. -> 외부에 있을 경우 0에서 2로 변환

우선 1번은 BFS 구현을 통해 처리해 주었다. 0,0부터 시작해 빈 공간일 경우 0에서 2로 바꾸어 주었다.

void Bfs(int start_n, int start_m) {
	// check out boundary 0 -> 2 
	queue<pair<int ,int> > q;
	q.push({start_n, start_m});
	
	while(!q.empty()) {
		pair<int, int> c = q.front();
		q.pop();
		// cout << c.first << " " << c.second << endl;
		if(paper[c.first][c.second] == 0)
			paper[c.first][c.second] = 2;
		
		else
			continue;
			
		if(c.first-1 >= 0)
			q.push({c.first-1, c.second});
		if(c.first+1 < n)
			q.push({c.first+1, c.second});
		if(c.second-1 >= 0)
			q.push({c.first, c.second-1});
		if(c.second+1 < m)
			q.push({c.first, c.second+1});
	}
}

 

2. 치즈가 외부에 닿아 있는지 확인

2, 3은 동시에 할 수도 있고, 따로 할 수도 있다. 필자는 2, 3을 따로 했다.

동시에 할 경우 -> n*m

따로 할 경우 -> 2*n*m (행렬을 두 번 도니까)

대신! 동시에 할 경우는 삭제 과정을 위해 다시 n*m 행렬을 돌면서 확인해야 한다. 결국 두 방법 모두 시간 복잡도는 비슷하다.

2, 3을 동시에 하면 4를 따로 해야 하고, 2, 3을 따로 하면 3, 4를 동시에 할 수 있다.

삭제할 치즈를 찾는다. -> 1에서 3으로 변경

bool Check_cheese() {
	bool tf = false;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(paper[i][j] == 1) {
				int cnt = 0;
				if(paper[i-1][j] == 2)
					cnt++;
				if(paper[i+1][j] == 2)
					cnt++;
				if(paper[i][j-1] == 2)
					cnt++;
				if(paper[i][j+1] == 2)
					cnt++;
					
				if(cnt >= 2) {
					paper[i][j] = 3;
					tf = true;
					// cout << i << " " << j << endl;
				}
			}
		}
	}
	if(tf)
		return true;
	return false;
}

 

3. 2칸 이상 닿아있는 치즈 삭제

4. 치즈가 삭제되면서 생긴 공간을 확인한다. 치즈가 삭제되면서 외부 공간과 내부 공간이 이어졌는지 확인한다. (1번을 다시 반복하면 됨)

삭제와 공간 확인을 동시에 한다.

void Delete_cheese() {
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(paper[i][j] == 3) {
				paper[i][j] = 0;
				Bfs(i, j);
			}
		}
	}
}

 

 

2~4 반복

 

최종 코드

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

int paper[100][100];
int n, m;

void Bfs(int start_n, int start_m) {
	// check out boundary 0 -> 2 
	queue<pair<int ,int> > q;
	q.push({start_n, start_m});
	
	while(!q.empty()) {
		pair<int, int> c = q.front();
		q.pop();
		// cout << c.first << " " << c.second << endl;
		if(paper[c.first][c.second] == 0)
			paper[c.first][c.second] = 2;
		
		else
			continue;
			
		if(c.first-1 >= 0)
			q.push({c.first-1, c.second});
		if(c.first+1 < n)
			q.push({c.first+1, c.second});
		if(c.second-1 >= 0)
			q.push({c.first, c.second-1});
		if(c.second+1 < m)
			q.push({c.first, c.second+1});
	}
}

bool Check_cheese() {
	bool tf = false;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(paper[i][j] == 1) {
				int cnt = 0;
				if(paper[i-1][j] == 2)
					cnt++;
				if(paper[i+1][j] == 2)
					cnt++;
				if(paper[i][j-1] == 2)
					cnt++;
				if(paper[i][j+1] == 2)
					cnt++;
					
				if(cnt >= 2) {
					paper[i][j] = 3;
					tf = true;
					// cout << i << " " << j << endl;
				}
			}
		}
	}
	if(tf)
		return true;
	return false;
}

void Delete_cheese() {
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(paper[i][j] == 3) {
				paper[i][j] = 0;
				Bfs(i, j);
			}
		}
	}
}

int main() {
	ios_base::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 >> paper[i][j];
		}
	}
	Bfs(0, 0);
	
	// check will delete cheese
	// if there is a cheese to remove, do while.
	int answer = 0;
	while(Check_cheese()) {
		Delete_cheese();
		answer++;
	}
	
	cout << answer;
}