[백준 7576] 토마토 - Python (그래프, BFS)

 

7576번: 토마토

 

<내 코드>

 

from collections import deque


def bfs():
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:

        now = queue.popleft()

        for i in range(4):
            nx = now[0] + direction[i][0]
            ny = now[1] + direction[i][1]

            if(0 <= nx < N) and (0 <= ny < M):
                if tomato[nx][ny] == 0:
                    tomato[nx][ny] = tomato[now[0]][now[1]] + 1 # 현재 요소 값에서 +1
                    queue.append((nx, ny))


M, N = map(int, input().split())
queue = deque()
tomato = []

# 토마토 상자 배열
for _ in range(N):
    tomato.append(list(map(int, input().split())))

# 값이 1인 요소들을 큐에 다 담기(동시 진행을 위한)
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append((i, j))

# 탐색 시작
bfs()

ans = 0
for i in range(N):
    for j in range(M):
        if ans < tomato[i][j]:
            ans = tomato[i][j]
        if tomato[i][j] == 0:
            print(-1)
            exit()
        ans = max(ans, 1) # 1과 배열의 최대값과 비교
print(ans - 1)

 

기존 BFS 문제를 풀던 거보다 조금 더 복잡한 문제였다. 이번 문제는 BFS 탐색 안에서 큐에 값을 넣고 또 탐색 전에 미리 큐에 좌표를 넣어주는 문제였다. 그렇게 해서 값이 1인 좌표값들을 동시에 탐색하도록 하는 것이다.