백준: 7576 토마토

문제

7576번: 토마토

 

문제 풀이

 익은 토마토와 안 익은 토마토가 인접해있다면 상, 하, 좌, 우로 한 칸씩 영향을 받아 토마토가 익게 된다. 상자에 토마토들의 정보가 주어졌을 때, 모든 토마토가 익는데 걸리는 날짜를 계산하여 반환하면 된다.

 

 위의 그림은 예제 입력 1이다. 예제 입력 1의 경우 토마토가 익는데 걸리는 시간은 8일이 소요된다. 이는 우측 하단에 있는 익은 토마토를 기준으로 그림과 같이 하루가 지남에 따라 대각선 방향으로 토마토들이 익기 때문이다. 따라서 단순히 상, 하, 좌, 우를 탐색하는 것이 아닌 동일한 날에 영향을 받은 것인지 판단하는 과정이 필요하다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < m and not graph[x][y]


def bfs():
    cnt = -1

    while q:
        cnt += 1

        for _ in range(len(q)):
            cur_x, cur_y = q.popleft()

            for x, y in dirs:
                next_x, next_y = x + cur_x, y + cur_y
                if visitable(next_x, next_y):
                    graph[next_x][next_y] = 1
                    q.append([next_x, next_y])

    unripe = [True for tomatoes in graph if 0 in tomatoes]

    return -1 if unripe else cnt


if __name__ == "__main__":
    m, n = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                q.append([i, j])

    print(bfs())

 이를 코드로 구현한다면, 현재 큐에 있는 토마토들을 모두 처리하여야 하루에 익을 수 있는 토마토들이 처리된 것이다. 따라서 다른 그래프 문제 들과 달리, 2중 반복문을 통해 처리해주어야한다는 점이 다르다.