백준 7576번 : 토마토 in Python

7576번: 토마토

 

www.acmicpc.net

위 문제는 토마토를 보관하는 창고에 토마토가 모두 익을 때까지 걸리는 날짜를 구하는 문제로, 토마토는 상하좌우에 익은 토마토가 있는 경우 익는다는 조건이 있다. 이는 익은 토마토를 출발점으로 해서 BFS를 실행해 익은 토마토를 늘려 나가면 된다.

이 방법을 좀더 자세히 설명하자면, 우선 익은 토마토 수를 저장하는 ripen 변수와 토마토가 없는 상자 수를 저장하는 blocked 변수를 만든다. 그리고 창고 내 모든 토마토 상자를 순회하면서 익은 토마토를 발견할 경우 BFS를 위한 queue에 해당 토마토의 인덱스와 시작 날짜를 의미하는 0을 가지는 배열을 넣고, ripen 변수를 1 증가시킨다. 만약 빈 토마토 상자를 발견할 경우 blocked 변수를 1 증가시킨다.

그 다음 창고 내 토마토가 모두 익는데 걸리는 날짜인 today 변수를 만들고 BFS를 실행한다. BFS는 queue의 원소인 배열을 하나 꺼낸다. 그리고 상하좌우 네 방향에 대해 인덱스가 범위 내에 들어있고 상자 안 토마토가 안 익은 토마토면 익은 토마토로 바꾸고, 이는 기존 토마토가 익은 날짜로부터 하루 뒤에 익게 되므로 queue에 배열을 추가할 때 인덱스와 함께 기존 토마토가 익은 날짜 + 1을 넣는다. 그리고 익은 토마토의 수는 하나 증가하므로 ripen을 1 증가시킨다.

이를 queue가 빌 때까지 반복하면 익은 토마토가 도달하지 못하는 상자를 제외하고 모든 토마토가 익게 된다. today 변수는 queue에서 원소를 하나 뽑을 때마다 해당 배열에 들어있는 날짜가 today가 다른 경우 today를 그 날짜로 바꾼다. 이렇게 하는 이유는 queue의 길이가 0이 돼 while loop을 종료하기 직전 마지막으로 queue에서 원소를 뽑으면 그 원소에 들어있는 날짜가 곧 모든 토마토가 다 익는데 걸리는 날짜와 같기 때문이다. 

while loop가 끝나면 이제 창고 내 모든 토마토가 다 익었는지 확인하기 위해 ripen의 값이 전체 상자들에서 blocked의 값을 뺀 결과와 같은지 확인하고 같으면 today를 출력하고 다르면 -1을 출력한다.

여기까지 구현했을 때 계속 시간 초과가 발생했었는데, 알고 보니 queue를 단순 list로 구현해서 queue의 pop(0)가 O(n) 시간만큼 걸렸기 때문이었다. 그래서 collections의 deque를 이용해 queue를 구현해 원소를 추출할 때 O(1) 시간만 걸리게 조정하니 시간 초과 문제가 해결되었다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
# deque를 통해 queue를 구현한다.
from collections import deque
# 동서남북 방향을 나타내는 배열
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
M, N = map(int, input().split())
tomatoes = [list(map(int, input().split())) for _ in range(N)]
queue = deque()
# 익은 토마토의 개수
ripen = 0
# 빈 상자의 개수
blocked = 0
for i in range(N):
    for j in range(M):
        if tomatoes[i][j] == 1:
            queue.append([i, j, 0])
            ripen += 1
        elif tomatoes[i][j] == -1:
            blocked += 1
# 모든 토마토가 익는데 걸린 날짜
today = 0
# BFS 구현
while len(queue) > 0:
    [i, j, k] = queue.popleft()
    # today를 구하는 코드
    if not k == today:
        today = k
    for l in range(4):
        next_i = i + dx[l]
        next_j = j + dy[l]
        if 0<=next_i<N and 0<=next_j<M and tomatoes[next_i][next_j] == 0:
            tomatoes[next_i][next_j] = 1
            queue.append([next_i, next_j, k + 1])
            ripen += 1
# 모든 토마토가 익은 경우에만 today를 출력한다.
if ripen == M*N - blocked:
    print(today)
else:
    print(-1)