1. 문제 설명

토마토

2. 문제 분석

탐색 가능한 노드가 1로, 그렇지 않은 노드가 -1로 주어진다. 주어진 위치에서 상하좌우로 이동할 때 모든 노드를 탐색할 수 있는지 확인하고, 가능하다면 걸리는 시간을 구한다.

1. BFS 또는 DFS를 통해 현재 그래프의 주어지 노드에서 -1을 제외한 나머지 노드에 다다를 수 있는지 확인하자.
2. 초기 상태에서 값이 1인 좌표를 모두 큐에 넣는다.
3. 상하좌우로 이동 가능한 다음 노드가 0인 경우 탐색하고, 그 노드에 다다르는 시간을 함께 큐에 넣는다.
4. 탐색이 끝난 뒤 그래프 좌표 중 0이 존재한다면 시작 노드에서 다다를 수 없는 노드가 존재한다는 뜻이다.
5. 모두 탐색 가능하다면 마지막으로 탐색한 노드까지 걸리는 시간을 반환한다.

• 시간 복잡도 측면에서 리스트보다 디큐(deque)가 매우 효율적이다. 탐색 알고리즘을 사용할 때 디큐를 활용하자.
• 그래프가 주어질 때 탐색 알고리즘을 통해 시작 상태에서 모두 탐색할 수 있는지, 즉 그래프 경로 여부가 존재하는지도 체크할 수 있다.
• 탐색 알고리즘에서 비용 역시 함께 확인할 수 있음을 꼭 기억하자.

3. 나의 풀이

from collections import deque

m, n = map(int, input().split())
nodes = [[] for _ in range(n)]
for i in range(n):
    nodes[i] = list(map(int, input().split()))
# 이차원 리스트로 그래프 표현

day = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
queue = deque([])

for i in range(n):
    for j in range(m):
        if nodes[i][j] == 1:
            queue.append([[i, j], day])
            # 초기 상태에서 '익은', 즉 이동 가능한 노드를 큐에 넣는다.

while queue:
    pos, day = queue.popleft()
    row, col = pos
    for x, y in zip(dx, dy):
        next_row, next_col = row+x, col+y
        if next_row < 0 or next_col < 0 or next_row > n-1 or next_col > m-1: continue
        # 현재 이동 가능 노드에서 상하좌우 이동했을 때 유효한 노드
        if nodes[next_row][next_col] == 0:
            # 방문한 적이 없다면 방문하고 이때 날짜까지 구하자.
            nodes[next_row][next_col] = 1
            queue.append([[next_row, next_col], day+1])

reachable = True
for i in range(n):
    for j in range(m):
        if nodes[i][j] == 0:
            # BFS 이후 0이 남아 있다면 처음 상태 주어진 노드에서 탐색할 수 없다는 뜻이다.
            reachable = False
            break

if not reachable: print(-1)
else: print(day)