[C++] BOJ(백준) 2636 치즈

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

2636번: 치즈

 

BFS와 구현이 함께 있는 문제다.

이 문제의 핵심은 치즈 안에 있는 공간을 어떻게 처리하느냐다.

처음에는 문제 파악을 제대로 하지 못하고 모든 0에 대하여 BFS를 진행했다.

이게 아님을 깨닫고... 치즈 속 공간을 어떻게 처리해야 하나 계속 고민했는데 혼자 깨닫기는 실패

구글링으로 힌트를 얻었다. 

 

나는 치즈를 BFS로 처리하려고만 했지 공기를 BFS로 처리하는 것은 생각도 못 했다.

이것이 해결 방안이었다.

 

테두리는 항상 치즈가 아니므로 (0, 0)부터 BFS를 시작하고

0과 인접한 1에 대해서 처리를 해주면 되는 것이다.

치즈는 한 시간동안 가장 바깥 테두리만 녹으므로 다 녹기까지 몇 시간이 걸리는 지는 BFS 실행 횟수로 구했다.

BFS를 실행할 때 마다 visit 함수가 초기화 되어야 하므로 memset 함수도 이용했다.

 

치즈의 크기는 테두리 치즈의 개수를 구했다.

치즈가 모두 녹기 전의 치즈는 테두리만 존재하기 때문이다.

 

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

int n, m, cnt;
int board[100][100];
int visit[100][100];
// 상하좌우 탐색을 위함
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int BFS() {
	int ccnt = 0;
	queue<pair<int, int>> q;

	// (0, 0)은 항상 공기
	q.push({ 0,0 });
	visit[0][0] = 1;
	
	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;

		q.pop();

		// 상하좌우 4방향 이동을 위함
		for (int i = 0; i < 4; i++) {
			int xx = curx + dx[i];
			int yy = cury + dy[i];

			// 범위를 벗어나면 continue
			if (xx >= n || xx < 0 || yy >= m || yy < 0) continue;

			// 방문한 적이 있으면 continue
			if (visit[xx][yy]) continue;

			// 공기면 큐에 push
			if (!board[xx][yy]) {
				q.push({ xx, yy });
				visit[xx][yy] = 1;
			}

			// 치즈면 공기로 바꿔줌, 치즈 count
			else if (board[xx][yy]) {
				board[xx][yy] = 0;
				visit[xx][yy] = 1;
				ccnt++;
			}
		}
	}
	return ccnt;
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) cin >> board[i][j];

	int cheese, before;
	while (1) {
		// visit 함수를 0으로 초기화하기 위함
		memset(visit, false, sizeof(visit));
		cheese = BFS();
		cnt++;	// 치즈가 모두 녹기까지의 시간 체크를 위함

		// 다 녹아서 0을 반환했다면 출력 후 종료
		if (!cheese) {
			cout << cnt - 1 << "\n" << before;
			break;
		}

		// 이전 치즈 크기를 기억하기 위함
		before = cheese;
	}
}

제출 결과가 종류별로 깔별로 나온게 웃겨서 다 올려둔다

 

오늘의 멍청함

1. visit[xx][yy]; 로 1을 지정 안해줘서 무한 반복 돌아감

2. BFS 상하좌우 범위 검사에서 xx, yy 모두 n으로 검사

3. 과정 보기 위해 적어놨던 cout 그대로 제출해서 출력초과

 

1, 2 번이 시간 엄청 잡아먹었다...^^