[BOJ] 2636 : 치즈 (C++)

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

2636번: 치즈

걸린 시간 : 47분 43초

---

생각이 너무 안 나서 답답했던 문제였다. 공기와 닿은 부분을 어떻게 찾을까 고민을 많이 했지만, 결국 실행마다 공기를 모두 찾아주고, 치즈를 모두 탐색해서 구현하는 것이었다. 이렇게 매 실행마다 해도, 실행은 최대 50번이고, 배열의 크기가 최대 100이라서 가능하다는 것을 알아차려야 했다.

 

알고리즘

배열은 0 ~ N+1 까지 있고 0과 N+1 부분은 가장자리이다. 사진에서 X 표시 부분이다. 즉 여기서 주의해야 할 점은, 여러가지 로직을 수행하는 범위가 0 ~ N-1 이 아니라 1 ~ N 이라는 것이다.

1. 입력 시 1 ~ N 부분을 채워야 한다. 0과 N+1 부분은 전역으로 생성해 0으로 채워져 있다. 이 때 총 치즈 개수를 세어 total 변수에 넣는다.
2. 이제 공기가 닿는 부분에는 0이 아니라 2로 계속 바꿔나갈 것이다. 우선 (0, 0)을 2로 바꿔준다.
3. while 문 안에서 다음을 반복한다. while문 마지막 즈음에 남은 치즈 개수를 확인해 다 먹었으면 그 때 break;한다.
   1. 먼저, 사진의 파란색 빗금 부분을 모조리 2로 채워야 한다. 이 부분은 DFS로 한다. 방문 체크를 위한 vis 배열은 실행 직전 0으로 초기화한다. (memset 함수를 사용하면 더 좋은 코드가 될 것 같다.)
   2. 시간을 증가시킨다.
   3. 모든 부분을 돌아보면서 치즈 부분 중에 주변에 공기가 있다면 willmelt 벡터에 삽입한다.
   4. total 변수에 willmelt의 크기를 빼서 남은 치즈 개수를 센다. 만약 0이라면 치즈가 다 녹은 것이므로 시간 (cnt)와 이번에 녹는 치즈 개수 (willmelt.size()) 를 출력하고 break; 한다.
   5. 치즈가 다 녹지 않았다면 willmelt 벡터에 있는, 즉 녹는 치즈 부분들을 공기가 채워졌다는 의미로 2로 바꿔준다.

정답코드

#include <bits/stdc++.h>
using namespace std;

int N, M, cnt, total;
int board[105][105];
int vis[105][105];
int di[4] = {-1, 0, 0, 1};
int dj[4] = {0, -1, 1, 0};

void pushair(int i, int j) {
	for (int k = 0; k < 4; k++) {
		int ni = i + di[k];
		int nj = j + dj[k];
		if (ni < 0 || ni > N+1 || nj < 0 || nj > M+1 || board[ni][nj] == 1 || vis[ni][nj] == 1)
			continue;
		vis[ni][nj] = 1;
		board[ni][nj] = 2;
		pushair(ni, nj);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) total++;
		}
	}
	if (total == 0) {
		cout << 0 << "\n" << 0;
		return 0;
	}
	board[0][0] = 2;
	while(1) {
		for (int i = 0; i <= N+1; i++) {
			fill(vis[i], vis[i]+M, 0);
		}
		vis[0][0] = 1;
		pushair(0, 0);
		vector<pair<int, int> > willmelt;
		cnt++;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (board[i][j] != 1) continue;
				if (board[i-1][j] == 2 || board[i+1][j] == 2 || board[i][j-1] == 2 || board[i][j+1] == 2) {
					willmelt.push_back({i, j});
				}
			}
		}
		total -= willmelt.size();
		if (total == 0) {
			cout << cnt << "\n" << willmelt.size();
			break;
		}
		for (auto coordinate : willmelt) {
			board[coordinate.first][coordinate.second] = 2;
		}
	}
	return 0;
}