[백준/Python] 7576 토마토

문제는 여기

코드

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

m,n = map(int, input().split()) #가로 세로
graph = [list(map(int, input().split())) for _ in range(n)]

#상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

queue = deque()
result = 0  # 며칠만에 익는지
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i,j,0))

while queue:
    x, y, cnt = queue.popleft()
    result = cnt
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
            graph[nx][ny] = 1
            queue.append((nx, ny, cnt + 1))

for item in graph:
    if 0 in item:
        result = -1

print(result)

기록할 점

일반적인 BFS/DFS 문제라고 생각하고 접근했었다

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

첫 번째 예제는 다음과 같았는데,
다른 예제에서도 당연히 1이 하나일 줄 알았다.

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

그래서 이 예제를 보고 답이 왜 6인지 의아해하는데에 많은 시간을 쏟았었다 ..
bfs를 시작하기 전에 토마토를 익힐 시작점을 다 queue에 넣어주고 시작하는 것으로 해결했다

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