[Python] BOJ/백준 7576번 토마토

[문제]

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

7576번: 토마토

[풀이]

이 문제는 지문에 나와있는 `최소 일수`,  `인접한 네 방향의 토마토가 익음` 키워드를 통해 bfs문제임을 알 수 있다.

최소 일수를 구하는 문제는 bfs를 이용한다.

 

나름의? 주의해야할 점은 첫 번째 날에 토마토 박스에 1이 여러 위치에 있을 경우 동시다발적으로 각 위치 주위의 토마토가 익어야하기 때문에 main에서 bfs 함수를 부를 때 상자에 저장된 토마토들의 초기 정보 한바퀴 전체를 돌아 deque에 담은 후 한번에 bfs 함수의 인자로 보내주었다.

 

여느 bfs 문제와 유사하지만 하루의 단위를 어떻게 세워야 하는지가 가장 중요한 포인트였던 것 같다.

나의 경우 temp_queue라는 여분의 데크를 만들어 하루동안 익은 토마토를 차례대로 넣은 후

미리 queue에 넣어둔(=어제 익었던 토마토) 토마토들이 다 pop 되어 큐가 비어있을 경우(: if not queue) 하루가 지난 것으로 간주했다. 따라서 이 경우 cnt 변수를 1 증가시키고 queue에 temp_queue를 옮겨담은 후 temp_queue를 빈 데크로 다시 초기화해준다.

 

[코드]

import sys
from collections import deque


def bfs(tomato):
    queue = tomato
    temp_queue = deque()
    cnt = 0

    # 왼쪽, 오른쪽, 앞, 뒤
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        y, x = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 해당 좌표가 범위를 넘지 않고, 그 좌표의 토마토가 익지 않은 경우(0)
            if 0 <= nx < m and 0 <= ny < n:
                if box[ny][nx] == 0:
                    temp_queue.append((ny, nx))
                    box[ny][nx] = 1
                    
        # queue가 비어있다면. 즉 하루가 끝나면 cnt 1 증가
        if not queue:
            cnt += 1
            queue.extend(temp_queue)
            temp_queue = deque()

    return is_all_ripe(cnt)

# 과일이 다 익었는지 확인. 0이 한개라도 있다면 -1 출력
def is_all_ripe(cnt):
    for i in range(n):
        for j in range(m):
            if box[i][j] == 0:
                cnt = 0
    return cnt - 1


m, n = map(int, sys.stdin.readline().split())
box = []
for _ in range(n):
    box.extend([list(map(int, sys.stdin.readline().split()))])

tomato = deque()
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            tomato.append((i, j))
print(bfs(tomato))