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

https://www.acmicpc.net/problem/7576

7576번: 토마토

풀이 과정

bfs를 이용해 미로찾기를 풀었던 것과 비슷하다.

'2178 - 미로탐색'을 먼저 풀어보는것이 좋다.

from collections import deque

M, N = map(int,input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

box = [] # 1 익은 토, 0 안익은 토, -1 빈 칸
day = [[0 for _ in range(M)] for _ in range(N)]

deq = deque()

for i in range(N):
    box.append([int(x) for x in input().split()])
    for j in range(M):
        if box[i][j] == 1:
            deq.append([i,j])

상하좌우를 입력하기 편하게 dx, dy 리스트를 선언해주고

토마토를 담을 상자 box리스트와 날짜를 기록할 day리스트를 선언한다.

 

이후 box에 토마토 정보를 입력하고 그중 익은 토마토를 deque에 추가한다.

 

while deq:
    x, y = deq.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if box[nx][ny] == 0:
                box[nx][ny] = 1
                day[nx][ny] = day[x][y] + 1
                deq.append([nx,ny])

이후 pop을 해고 각 좌표에 대해 상하좌우로 0인지 확인하면서 deque에 추가한다.

동시에 day리스트도 업데이트 해준다. 날짜가 지날때 마다 토마토가 상하좌우로 퍼져나가기 때문에

익은 토마토 날짜(day[x][y])에 + 1 해주면 된다.

zeroflag = False
resultday = 0
for i in range(N):
    for j in range(M):
        if box[i][j] == 0:
            zeroflag = True

마지막으로 출력조건을 맞춘다.

 

출력조건에서 입력할때 이미 모든 토마토가 익었으면 0, 익지못한 토마토가 존재하면 -1

이외의 경우는 모든 토마토가 익을때까지 걸린 날을 출력한다.

 

zeroflag 변수를 만들어서 익지 못한 토마토가 존재하는지 확인해준다.

동시에 day리스트에서 최대값을 확인해준다. 이미 입력때 모든 토마토가 익었다면 최대값은 0이다.

 

이후 익지못한 토마토 유무에 따라 출력해주면 된다.