[백준] 7576번 : 토마토 (파이썬)

문제

나의 답안

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

m,n=map(int,input().split())

arr=[]
for _ in range(n):
    arr.append(list(map(int,input().split())))#토마토 있는 곳

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

for i in range(n):
    for j in range(m):
        if arr[i][j]==1:#토마토가 있다면
            que.append((i,j))#해당 위치 큐에 추가

while que:
    x,y=que.popleft()#갈 수 있는 곳의 좌표
    for i in range(4):#상하좌우 탐색
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<m and arr[nx][ny]==0:#익지않은 토마토+좌표 내
            que.append((nx,ny))#덱큐에 추가하고
            arr[nx][ny]=arr[x][y]+1#증가

for k in arr:
    for kk in k:
        if kk==0:
            print(-1)#불가능한 상황
            sys.exit(0)#더 둘러보지 않고 종료
    day=max(day,max(k))#모든 토마토가 익음
print(day-1)

유사문제 2178번 미로 탐색
접근 방법

• 최소일수를 구하기 위해 BFS를 이용한다.
• 토마토 값을 입력받고, 토마토가 있는 곳의 값을 큐에 추가해준다.
• while문을 통해 갈 수 있는 곳의 좌표를 큐에 저장해준다.(모든 값 탐색)
  • 좌표 안에 익지 않은 토마토가 있다면 해당 좌표의 값을 1증가시킨다.(익은 토마토로 변환)
• while문을 통해 모든 좌표를 탐색했다면 이중 반복문을 통해
  • 토마토가 익을 수 없다면 -1을 출력하고 프로그램 종료(exit(0))
  • 아니라면 day를 갱신시킨다.
• 날짜 계산 시 첫날을 포함하므로 -1을 해준 값을 출력한다.