[Baekjoon] 2638번: 치즈

🥅 문제

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

 

🔍 설계

치즈가 닿아있는 블럭이 2개 이상이면 녹을 예정이다. 치즈 내부에 있는 공기는 치즈에 영향을 줄 수 없다. 모눈종이의 맨 가장자리들은 치즈가 놓이지 않는다고 했으므로, 그 중 대표적인 (0, 0) 에서 시작하여 외부 공기의 영향력을 행사한다. 

 

외부 공기의 영향력을 행사하는 방법은 BFS를 이용하여 치즈가 놓인 곳에 2번 방문했을 때, 1시간 후에 녹으면서 새롭게 영향력을 행사할 수 있는 외부 공기 후보들의 모임인 next_q에 추가하는 것이다. 만약 next_q에 아무것도 추가되지 않는다면 그대로 종료되고, 추가된 것이 있다면 1초를 증가시킨다. next_q에 추가하는 이유는 치즈가 녹는 과정은 1시간 후에 동시에 이루어져야 하기 때문도 있다.

 

👊 풀이

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

int n, m, result = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<vector<int>> paper(100, vector<int>(100));
vector<vector<int>> visited(100, vector<int>(100));

void bfs() {
	queue<pair<int, int>> q;
	queue<pair<int, int>> next_q;
	q.push({ 0, 0 });
	visited[0][0] = 1;

	while (true) {
		while (!q.empty()) {
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int new_x = cur_x + dx[i];
				int new_y = cur_y + dy[i];
				if (!(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)) {
					continue;
				}
				if (paper[new_x][new_y] == 0 && visited[new_x][new_y] == 0) {
					visited[new_x][new_y] += 1;
					q.push({ new_x, new_y });
				}
				else if (paper[new_x][new_y] == 1) {
					visited[new_x][new_y] += 1;
					if (visited[new_x][new_y] == 2) {
						next_q.push({ new_x, new_y });
					}
				}
			}
		}
		if (next_q.empty()) {
			break;
		}
		else {
			result += 1;
		}

		while (!next_q.empty()) {
			int new_x = next_q.front().first;
			int new_y = next_q.front().second;
			q.push(next_q.front());
			next_q.pop();
			paper[new_x][new_y] = 0;
		}
	}
	
	
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

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

	bfs();

	cout << result << "\n";
	
	return 0;
}