7576 토마토 그래프

실1

bfs 문제이다.

생각보다 간단한 원리로 풀린다.

먼저 전체 배열을 순회하면서 1, 즉 익은 토마토를 모두 queue에 삽입한다.

이후 queue를 순회하면서 0 (안 익은 토마토) 가 있을 경우 queue에 삽입하는 걸 반복한다. 탐색한 부분은 1로 바꿔줌으로써 더 이상 count를 하지 않도록 해준다.

이렇게 queue가 모두 없어질 때까지 순회하면 모든 1에서 0으로 연결될 수 있는 포인트를 모두 탐색하게 된다. 그리고 queue에서 마지막으로 빠져나오는 count 값을 출력해주면 된다.

불가능한 부분이 있는 경우를 확인하기 위하여, 마지막에 모든 배열을 순회하면서 0이 있는지 확인해준다.

개인적으로 가로 세로 이동 코드는 미리 짜놓고 복붙하는게 좋은 것 같다. 미로탐색 문제에서 그대로 가져와도 적용이 간단했다.

from collections import deque

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

def solution():

    dq = deque([])

    for i in range(M):
        for j in range(N):
            if arr[j][i] == 1:
                dq.append([[i,j], 0])

    while dq:
        temp, count = dq.popleft()

        right = temp[0]+1
        left = temp[0]-1
        up = temp[1]-1
        down = temp[1]+1

        if right < M:
            if arr[temp[1]][right] == 0:
                dq.append([[right, temp[1]], count + 1])
                arr[temp[1]][right] = 1

        if down < N:
            if arr[down][temp[0]] == 0:
                dq.append([[temp[0], down], count + 1])
                arr[down][temp[0]] = 1

        if left >= 0:
            if arr[temp[1]][left] == 0:
                dq.append([[left, temp[1]], count + 1])
                arr[temp[1]][left] = 1

        if up >= 0:
            if arr[up][temp[0]] == 0:
                dq.append([[temp[0], up], count + 1])
                arr[up][temp[0]] = 1

    for i in range(M):
        for j in range(N):
            if arr[j][i] == 0:
                print(-1)
                return
    print(count)

solution()