BOJ - 2638번 치즈, BFS를 이용한 풀이 정리

이번 문제는 BFS 혹은 DFS와 같은 그래프 탐색 알고리즘을 이용하여, 이후 상황에 대한 시뮬레이션 과정을 구현하는 문제였습니다.

2638번: 치즈

 

위와 같이 주어진 모눈종이에서 외부 공기와 2개의 면 이상이 닿아있는 치즈는 녹는 상황에서 치즈가 모두 녹는데 걸리는 시간을 구하는 문제입니다.

---

간단한 그래프 탐색 문제처럼 단순하게 순회를 해서 해결되는 문제가 아니었고, 시간의 흐름을 측정할 수 있어야 했습니다.

 

그 이유는 그 시간대에서 녹을 위치에 있는 치즈가 모두 녹고난 다음에 다음 치즈가 녹기 시작하기 때문입니다.

 

따라서 치즈가 녹는 타이밍 하나하나가 곧 시간의 흐름을 의미하기 때문에, 다음과 같은 생각을 갖고 구현을 했습니다.

• 현재 외부 공기를 큐에 넣고 지금 시점을 기준으로 녹게될 치즈를 melted_cheese vector에 넣어둔다.
• BFS 방식으로 한번의 탐색을 마치고난 뒤에 queue가 비게 되면, melted_cheese에 있는 지금 시점에서 녹은 치즈를 외부 공기로 취급해서 queue에 넣어준다.
• queue와 melted_cheese vector가 모두 빌때까지 위 과정을 반복한다.

---

제출한 코드

#include <iostream>
#include <queue>

#define MAX 101

using namespace std;

typedef pair<int, int> node;

int n, m;

int map[MAX][MAX];
int val[MAX][MAX];
bool visited[MAX][MAX];

vector<node> melted_cheese;

bool inRange(int x, int y) {
‌return (0 <= x && x < n && 0 <= y && y < m);
}

int bfs() {
‌queue<node> q;

‌int dx[] = { -1, 1, 0, 0 };
‌int dy[] = { 0, 0, -1, 1 };

‌int curHour = 0;
‌
‌q.push({ 0, 0 });
‌visited[0][0] = true;

‌while (!q.empty()) {
‌‌int x = q.front().first;
‌‌int y = q.front().second;
‌‌q.pop();

‌‌for (int i = 0; i < 4; i++) {
‌‌‌int nx = x + dx[i];
‌‌‌int ny = y + dy[i];

‌‌‌if (!inRange(nx, ny))
‌‌‌‌continue;

‌‌‌// 공기인 경우 (새로운)
‌‌‌if (map[nx][ny] == 0 && !visited[nx][ny]) {
‌‌‌‌visited[nx][ny] = true;
‌‌‌‌q.push({ nx, ny });
‌‌‌}
‌‌‌// 치즈인 경우
‌‌‌else if (map[nx][ny] == 1) {
‌‌‌‌// 외부 공기와 두 군데 이상 접촉된 경우
‌‌‌‌if (++val[nx][ny] >= 2 && !visited[nx][ny]) {
‌‌‌‌‌visited[nx][ny] = true;
‌‌‌‌‌melted_cheese.push_back(node(nx, ny));
‌‌‌‌}
‌‌‌}
‌‌}

‌‌//큐가 비었고, 지금 턴에 녹은 치즈가 있는 경우
‌‌if (q.empty() && !melted_cheese.empty()) {
‌‌‌curHour++;
‌‌‌for (auto it = melted_cheese.begin(); it != melted_cheese.end(); it++) {	
‌‌‌‌//녹은 치즈는 공기가 되었다.
‌‌‌‌q.push({ it->first, it->second });
‌‌‌‌map[it->first][it->second] = 0;
‌‌‌}
‌‌‌melted_cheese.clear();
‌‌}
‌}

‌return curHour;
}

int main() {
‌ios::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 >> map[i][j];
‌‌}
‌}
‌
‌cout << bfs();

‌return 0;
}

---

참고

 

[BFS] 2638번 치즈