7576번 - 토마토

💡 BFS의 새로운 유형 익혀보자!

import sys
from collections import deque

input = sys.stdin.readline

M, N = map(int, input().split())

graph = []
visited = [[False] * M for _ in range(N)]
day = 0

for _ in range(N):
    graph.append(list(map(int, input().split())))

def bfs():
    dq = deque()
    
    # 익은 토마토의 위치를 미리 전부 저장해둔다.
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                dq.append((j, i))
                visited[i][j] = True
    
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    
    while dq:
        x, y = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            
            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 0 and not visited[ny][nx]:
                dq.append((nx, ny))
                visited[ny][nx] = True
                graph[ny][nx] = graph[y][x] + 1

bfs()

for k in range(N):
    if 0 in graph[k]:
        print(-1)
        exit()
    day = max(day, max(graph[k]))

print(day - 1)

• 위 문제는 생각보다 삽질을 많이 한 문제였다..ㅎ
• 일단 입력이 0과 1, -1로 구성된 배열 형태로 들어오기도 했고, 최소 날짜를 출력해야 하기 때문에 BFS로 접근해봐야 겠다고 생각했다.
• 핵심 포인트는 기존 유형처럼 값이 1인 x,y를 돌아가면서 넣어주는 것이 아니라, 처음에 쭉 순회하면서 토마토의 위치를 dq에 넣어주는 것이다.
• 토마토의 위치를 처음에 dq에 넣어주고, 해당 시점들을 중심으로 확장하였고, 익은 날짜의 최소 날짜를 구해야함으로, 확장하면서(하루가 지날 때마다) +1을 넣어주었다.
• 마지막으로 배열을 쭉 돌면서 0이 있으면(즉, 안 익은 토마토가 있으면) -1을 출력해주고, 그렇지 않으면 가장 큰 값 (즉 최대한 많은 수의 토마토를 익혔을 날짜)을 출력해준다.