백준 7576번: 토마토

백준 7576번: 토마토

아이디어

전형적인 BFS 문제다. 맨 처음 시작할 때 익은 토마토가 위치한 지점들을 deque에 넣고, 상하좌우 한 칸씩 탐색하며 익지 않은 토마토가 있는 경우 익히고 그 위치도 deque에 넣는다. 이 때 익은 토마토를 모두 1로 표시하기보단 2, 3, 4.. 이렇게 순서대로 표시하면 모든 토마토가 익는데 걸린 날짜를 쉽게 구할 수 있다.

이렇게 날짜가 표시된다. 0일부터 시작하므로 마지막으로 방문한 graph[row][col]에서 1을 빼주면 정답이다.

코드

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

M, N = map(int, input().split())
tomatoBox = [list(map(int, input().split())) for _ in range(N)]
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]


def bfs(graph):
    row, col = 0, 0
    dq = deque()
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                dq.append([i, j])

    while dq:
        row, col = dq.popleft()
        for i in range(4):
            if 0 <= row + dy[i] < N and 0 <= col + dx[i] < M:
                if graph[row + dy[i]][col + dx[i]] == 0:
                    dq.append([row + dy[i], col + dx[i]])
                    graph[row + dy[i]][col + dx[i]] = graph[row][col] + 1

    for i in graph:
        if 0 in i:
            return -1
    return graph[row][col] - 1


print(bfs(tomatoBox))

여담

처음에 DFS로 풀면서 삽질함. 문제를 보자마자 어떻게 풀어야 하는지 알 수 있을 정도로 연습해야겠다.

백준 7569번: 토마토문제는 비슷한 문제인데 3차원 리스트를 사용하면 된다.

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

M, N, H = map(int, input().split())
tomatoBox = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]

dy = [1, -1, 0, 0, 0, 0]
dx = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]


def bfs(graph):
    height, row, col = 0, 0, 0
    dq = deque()
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if graph[i][j][k] == 1:
                    dq.append([i, j, k])

    while dq:
        height, row, col = dq.popleft()
        for i in range(6):
            if 0 <= height + dz[i] < H and 0 <= row + dy[i] < N and 0 <= col + dx[i] < M:
                if graph[height + dz[i]][row + dy[i]][col + dx[i]] == 0:
                    dq.append([height + dz[i], row + dy[i], col + dx[i]])
                    graph[height + dz[i]][row + dy[i]][col + dx[i]] = graph[height][row][col] + 1

    for i in graph:
        for j in i:
            if 0 in j:
                return -1
    return graph[height][row][col] - 1


print(bfs(tomatoBox))