[BOJ/PYTHON] gold5-7576. 토마토

백준 문제 링크: https://www.acmicpc.net/problem/7576

문제 요약

토마토가 모두 익는 데 걸리는 최소 일수 (익은 토마토와 인접하면 1일 후 익음)

토마토의 상태: 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸

핵심 아이디어

바이러스를 감염시키는 것과 같은 bfs 문제이다.

익은 토마토가 감염원이므로 값이 1(처음부터 익은 토마토)인 좌표를 큐에 넣고 시작한다.

bfs를 돌면서 익지 않은 토마토를 발견하면 큐에 넣어주고 값을 1 더해준다. 이때, 새로 방문한 익지 않은 토마토 자리에 그 값을 그대로 1 더해주는 게 아니라 감염시키는 좌표의 값에서 1을 더해줘야 한다. (array[nx][ny] += 1이 아니라 array[nx][ny] = array[a][b] + 1)

bfs를 했는데도 익지 않은 토마토가 남아있으면 모든 토마토를 익히는 것에 실패했으니 -1을 출력하고, exit()으로 빠져나와준다. 그게 아니면 최대값을 갱신하면서 출력해주면 된다.

풀이

# gold5-7576. 토마토

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

m, n = map(int, input().split()) # 가로 세로
array = [list(map(int, input().split())) for _ in range(n)] # 상자에 담긴 토마토
day = 0 # 걸리는 최소 일자
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
q = deque()

for x in range(n):
    for y in range(m):
        # 익은 토마토
        if array[x][y] == 1:
            q.append((x, y))

def bfs():
    while q:
        a, b = q.popleft()
        for i in range(4):
            nx, ny = a + dx[i], b + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 빈 곳 방문
                if array[nx][ny] == 0:
                    array[nx][ny] = array[a][b] + 1
                    q.append((nx, ny))

bfs()

for x in range(n):
    for y in range(m):
        # 다 돌렸는데도 안 익은 게 남아있음
        if array[x][y] == 0:
            print(-1)
            exit()
    # 한 줄 기준 최대값과 그동안의 최대값 비교해 갱신
    day = max(day, max(array[x]))        

# 토마토 시작점이 1이었으니 다시 빼줌
print(day - 1)

실행 시간

메모리 98588KB, 시간 1532ms (python3)