[백준/Python] 7576 토마토

문제 링크

7576번: 토마토

 

문제 풀이

• 일반적인 bfs 문제와는 조금 다르게 시작점(익은 토마토)의 위치가 1개 이상이라는 점이다.
• 처음으로 얻은 익은 토마토의 위치를 큐에 넣은 후 너비 우선 탐색을 진행하면, 해당 시작점에 대해 너미 우선 탐색을 모두 진행한다. 이후에 큐에 새로운 익은 토마토의 위치가 추가되고 다시 너비 우선 탐색을 수행해야 할 경우, 기존에 방문한 위치를 다시 방문하는 문제가 발생하므로 다른 방법으로 접근해야 한다.
• 따라서 익은 토마토의 위치는 큐에 모두 넣은 뒤에 너비 우선 탐색을 진행하면 된다.

 

전체 코드

import sys
from collections import deque

def bfs():
    while queue:
        x, y = queue.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 t[nx][ny] == 0 and not visited[nx][ny]:
                t[nx][ny] += t[x][y] + 1
                visited[nx][ny] = True
                queue.append((nx, ny))

m, n = map(int, sys.stdin.readline().split())
t = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

visited = [[False] * m for _ in range(n)]

queue = deque()

for i in range(n):
    for j in range(m):
        if t[i][j] == 1:
            t[i][j] = 0
            queue.append((i, j))
            visited[i][j] = True

bfs()

day = 0
for i in t:
    if max(i) > day:
        day = max(i)

for i in range(n):
    for j in range(m):
        if t[i][j] == 0:
            if not visited[i][j]:
                day = -1

print(day)