BOJ 7576 · 토마토

알고리즘 분류 : BFS  

익은 토마토는 인접하면서 아직 익지 않은 토마토를 익게 만든다. 하루에 1칸 인접한 토마토만 익게 만들 때, 모두 익게 만드는 최소 일수를 구하는 문제이다. 다르게 말하면, 간선 길이가 1인 그래프에서 최단 거리를 구하는 문제와 비슷하다. 즉, BFS를 사용하면 된다.

• 우선 토마토 배열을 입력받는다. 1은 이미 익은 토마토이므로 입력받으면서 Queue에 집어 넣는다.
• 토마토를 익힐 때, 인접한 4칸(상하좌우)을 확인해야 한다. 이때, 0인지 아닌지 확인하고, 0이면 익게 만든다.
• 토마토 배열은 날짜 카운트 배열로 사용 가능하다. 처음부터 익은 토마토는 1, 다음 날 익은 토마토는 1+1, 그 다음 날은 2+1, ··· 순으로 1일씩 증가시킨다.
• BFS를 통해 인접한 토마토를 모두 익혔으므로, 비어있는 칸(-1)으로 막혀있는 토마토는 익히지 못한다.
• 정답을 낼 때 다시 N x M for문으로 확인해보면서 아직 익지 않은 토마토(0)가 있으면 -1을 출력하고 종료한다.
• 익지 않은 토마토가 없으면, 배열에서 가장 큰 값을 출력한다. 이 값은 모든 토마토가 익은 마지막 날이다. 1부터 시작했으므로, 값에 -1을 빼야 한다.

---

C++ 소스코드

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

struct tomato {
    int x, y;
};

int m, n, ans;
int a[1001][1001];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<tomato> q;

void bfs() {
    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 (a[nx][ny]) continue;
            a[nx][ny] = a[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

int main() {
    scanf("%d %d", &m, &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 1) {
                q.push({i, j});
            }
        }
    }
    bfs();
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (a[i][j] == 0) {
                printf("-1\n");
                return 0;
            }
            if (ans < a[i][j]) ans = a[i][j];
        }
    }
    printf("%d\n", ans-1);
    return 0;
}

---

Python 3 소스코드

import sys
from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
m, n = map(int, sys.stdin.readline().split())
a = []
q = deque()
for i in range(n):
    a.append(list(map(int, sys.stdin.readline().split())))
    for j in range(m):
        if a[i][j] == 1:
            q.append((i, j))

def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if a[nx][ny]:
                continue
            a[nx][ny] = a[x][y] + 1
            q.append((nx, ny))

def solve():
    bfs()
    ans = 0
    for i in range(n):
        if 0 in a[i]:
            return -1
        ans = max(ans, max(a[i]))
    return ans-1

print(solve())

---

참고

• 백준 온라인 저지 : BOJ 7576