[Python] 백준/BOJ 7576번: 토마토 (Gold 5)

💻 Problem

문제 보러 가기

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

각 칸은 익은 토마토(1), 익지 않은 토마토(0), 빈칸(-1) 중 하나이다.

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳(상하좌우)에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

 

💡 Approach

1. 익은 토마토가 있는 칸들을 찾아서 큐에 위치를 저장한다.
2. 익은 토마토가 있는 칸에서 탐색을 시작한다.
3. 현재 위치에서 상하좌우 칸을 살펴본다.
4. 다음 칸에 안 익은 토마토가 있으면 토마토를 익게 만든다.
   1. 토마토를 익게 하는데 하루가 소요된다.
   2. 토마토가 익은 날짜를 해당 칸에 기록한다. (이전 칸 + 1)
5. 박스에서 가장 큰 숫자가 기록되어 있는 칸을 찾는다.

 

5번에서 찾은 칸에 기록된 숫자가 모든 토마토가 익는 데에 걸리는 최소 날짜이다.

처음 익은 토마토 칸이 1이므로 걸린 날짜는 하루를 빼야 한다.

 

✏️ Solution

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

def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        x, y = queue.popleft()

        # 상하좌우를 탐색한다
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어나면 탐색하지 않는다
            if nx < 0 or nx >= row_size or ny < 0 or ny >= col_size:
                continue

            # 안익은 토마토가 있는 칸이면 하루를 더해서 기록한다
            # 다음 토마토를 탐색한다
            if box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                queue.append((nx, ny))

col_size, row_size = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(row_size)]
queue = deque()
days = 0 # 토마토가 모두 익을 때까지의 최소 날짜

# 익은 토마토가 있는 칸을 모두 찾아 위치를 저장한다
for i in range(row_size):
    for j in range(col_size):
        if box[i][j] == 1:
            queue.append((i, j))

bfs()

for row in box:
    # 토마토가 모두 익지는 못하는 상황이면 -1을 출력한다
    if 0 in row:
        print(-1)
        exit(0)
    days = max(days, max(row))

# 시작이 1이므로 하루는 제외한다
print(days - 1)

시간복잡도: O(row_size * col_size)

row_size와 col_size의 최댓값은 1,000이다.

1,000 * 1,000 = 1,000,000 = 10 ^ 6

1억(10 ^ 8) 보다 작으므로 시간제한 1초에 문제 되지 않는다.