BOJ 2638 · 치즈

알고리즘 분류 : BFS  

치즈가 완전히 녹기까지 걸리는 시간을 구하는 문제다. 치즈는 한 칸에 놓이며, 인접한 칸에 외부 공기(0)가 2칸 이상 있다면, 녹는다. 내부 공기는 치즈에 영향을 주지 않으므로 유의해야 한다.

• 입력으로 주어지는 맵은 가장자리가 항상 외부 공기(0)로 주어진다.
• 따라서 (0, 0)이 항상 공기 칸이므로, BFS의 시작을 (0, 0)으로 한다.
• 인접한 상하좌우 칸이 공기(0)라면, 이동한다.
• 인접한 칸이 치즈(1)라면, 치즈를 1만큼 증가시킨다.
• BFS 탐색이 완료되면, 치즈는 1 이상의 값으로 된다.
• 이때, 치즈 값이 3 이상이라면, 2번 이상 외부 공기에 닿은 것이므로, 치즈를 녹여서 공기 칸(0)으로 만든다.
• 치즈 값이 2라면, 외부 공기에 한 번만 닿은 것이므로, 1로 다시 되돌려 놓는다.
• 치즈가 완전히 녹을 때까지 BFS를 반복한다.

---

C++ 소스코드

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

struct cheese {
    int x, y;
};

int n, m, ans;
int a[100][100];
bool check[100][100];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

void bfs() {
    memset(check, false, sizeof(check));
    queue<cheese> q;
    q.push({0, 0});
    check[0][0] = true;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (check[nx][ny]) continue;
            if (a[nx][ny] >= 1) {
                a[nx][ny] += 1;
                continue;
            }
            q.push({nx, ny});
            check[nx][ny] = true;
        }
    }
}

bool melt() {
    bool melted = false;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (a[i][j] >= 3) {
                a[i][j] = 0;
                melted = true;
            } else if (a[i][j] == 2) a[i][j] = 1;
        }
    }
    return melted;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    while (true) {
        bfs();
        if (melt()) ans++;
        else break;
    }
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

def bfs():
    q = deque()
    q.append((0, 0))
    check = [[False]*m for _ in range(n)]
    check[0][0] = True
    while q:
        x, y = q.popleft()
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not check[nx][ny]:
                if a[nx][ny] >= 1:
                    a[nx][ny] += 1
                else:
                    q.append((nx, ny))
                    check[nx][ny] = True

def melt():
    melted = False
    for i in range(n):
        for j in range(m):
            if a[i][j] >= 3:
                a[i][j] = 0
                melted = True
            elif a[i][j] == 2:
                a[i][j] = 1
    return melted


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
while True:
    bfs()
    if melt():
        ans += 1
    else:
        break
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 2638