백준 - 토마토 (BFS)

백준 토마토

• 멋쟁이 토마

해결 과정

• 미로 탐색과 매우 유사한 문제이다.
• 미로 탐색과 다른 점이 있으면 시작 위치가 여러개라는 점이다.
• 따라서 시작위치를 queue에 넣어놓고 시작한다.
• 출력할 때 조심할 점은 0이 하나라도 있으면 -1로 리턴해야한다
• exit()를 써서 하나 발견해버리면 프로그램을 종료 하자.

BFS 해결

from collections import deque

N, M = map(int, input().split())
lst = []
for i in range(M):
    lst.append(list(map(int,(input().split()))))

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

queue = deque()

for i in range(M):
   for j in range(N):
       if lst[i][j]==1:
           queue.append((i, j))

while queue:
    x, y = queue.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        # 지역 밖을 벗어나거나, 벽일 경우에 차단            
        if nx < 0 or nx >= M or ny < 0 or ny >= N or lst[nx][ny]==-1 :
            continue
        # 0을 만났을 경우
        if lst[nx][ny] == 0:
            # 1을 만난 친구에게 -> 나의 값 +1
            lst[nx][ny] = lst[x][y] +1
            # 새로 만난 친구의 좌표를 queue에 저장
            queue.append((nx, ny))

for i in range(M):
   for j in range(N):
        if lst[i][j]==0:
            print(-1)
            exit()
    
print(max(map(max, lst)) - 1)