취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2636번 문제인 치즈이다.
문제는 아래 링크를 확인하자.

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

매 분마다 (0,0)서부터 bfs등을 이용해 밖에 노출되어있는 치즈 칸들이 무엇인지를 모두 구할 수 있으므로, 분 단위로 어떤 치즈가 녹는지 직접 시뮬레이션을 돌려보자.

만약 밖에 노출되어있는 치즈칸이 더 없다면 이전 분이 치즈가 남아있던 마지막 순간이 되고, 아니라면 이번 분에 녹는 치즈 칸 수를 기록하고 밖에 노출되어있는 치즈칸들을 빈 칸으로 바꾸는 것을 반복하자.

모든 치즈는 100분 안에 녹을 것이고 주어지는 판에는 많아야 10000개의 칸과 40000개 이하의 에지가 있으므로 제한시간 내에 충분히 위의 시뮬레이션을 마칠 수 있다.

아래는 제출한 소스코드이다.

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

int R, C;
bool cheese[100][100];
int visited[100][100];

int dr[4] = { 1,-1,0,0 }, dc[4] = { 0,0,1,-1 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) cin >> cheese[r][c];
	}

	int TURN = 0, old = 0;
	queue<pair<int, int>> que;
	while (1) {
		memset(visited, 0, sizeof(visited));
		queue<pair<int, int>> bfsque;
		bfsque.push(make_pair(0, 0));
		while (!bfsque.empty()) {
			int r = bfsque.front().first, c = bfsque.front().second; bfsque.pop();
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
				if (visited[rr][cc]) continue;
				visited[rr][cc] = 1;
				if (cheese[rr][cc]) que.push(make_pair(rr, cc));
				else bfsque.push(make_pair(rr, cc));
			}
		}
		if (que.empty()) break;
		TURN++;
		old = que.size();
		while (!que.empty()) {
			auto& p = que.front();
			cheese[p.first][p.second] = 0;
			que.pop();
		}
	}

	cout << TURN << '\n' << old;
}