Yunsu's Log

BOJ 7576: 토마토

7 min read

Note

다중 시작점 BFS를 활용하여 여러 개의 익은 토마토에서 동시에 퍼져나가는 최소 일수를 구하는 문제입니다.

문제 링크

문제 요약

격자 모양 상자에 토마토를 보관합니다. 익은 토마토(1)는 하루가 지나면 인접한 익지 않은 토마토(0)를 익게 만듭니다. 모든 토마토가 익을 때까지의 최소 일수를 구하세요.

  • 입력: 상자의 크기 M, N과 토마토 상태 (1: 익은 토마토, 0: 익지 않은 토마토, -1: 빈 칸)
  • 출력: 모든 토마토가 익을 때까지의 최소 일수 (이미 모두 익어있으면 0, 모두 익을 수 없으면 -1)

핵심 아이디어

다중 시작점 BFS

이 문제의 핵심은 여러 개의 시작점에서 동시에 BFS를 시작하는 것입니다.

  1. 모든 익은 토마토를 큐에 먼저 추가
  2. BFS를 통해 인접한 토마토를 익게 만들면서 거리(일수)를 저장
  3. 모든 토마토가 익었는지 확인하고 최대 일수 반환

왜 다중 시작점 BFS인가?

  • 단일 시작점 BFS: 한 곳에서 시작하여 최단 거리 계산
  • 다중 시작점 BFS: 여러 곳에서 동시에 시작하여 각 위치까지의 최소 거리 계산

토마토 문제에서는 여러 개의 익은 토마토가 동시에 영향을 주므로, 모든 익은 토마토를 시작점으로 설정해야 합니다.

알고리즘 설계

1. 초기화

queue = deque([])
 
# 모든 익은 토마토를 큐에 추가
for y in range(n):
    for x in range(m):
        if grid[y][x] == 1:
            queue.append((y, x))

2. BFS 탐색

offset = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우
 
while queue:
    v = queue.popleft()
    value = grid[v[0]][v[1]]
    
    for d in offset:
        dy = v[0] + d[0]
        dx = v[1] + d[1]
        
        if 0 <= dy < n and 0 <= dx < m:
            if grid[dy][dx] == 0:  # 익지 않은 토마토
                queue.append((dy, dx))
                grid[dy][dx] = value + 1  # 일수 저장

3. 결과 확인

max_value = 0
is_zero = False
 
for y in range(n):
    for x in range(m):
        if grid[y][x] == 0:  # 익지 않은 토마토가 남아있음
            is_zero = True
        max_value = max(max_value, grid[y][x])
 
if is_zero:
    print(-1)  # 모두 익을 수 없음
else:
    print(max_value - 1)  # 최대 일수 (시작이 1이므로 -1)

전체 코드

import sys
from collections import deque
 
readline = sys.stdin.readline
 
m, n = map(int, input().split())
 
grid: list[list[int]] = []
 
for _ in range(n):
    row = list(map(int, readline().split()))
    grid.append(row)
 
queue = deque([])
for y in range(n):
    for x in range(m):
        if grid[y][x] == 1:
            queue.append((y, x))
 
# 상하좌우 방향
offset = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
while queue:
    v = queue.popleft()
    value = grid[v[0]][v[1]]
    for d in offset:
        dy = v[0] + d[0]
        dx = v[1] + d[1]
 
        if 0 <= dy and dy < n and 0 <= dx and dx < m:
            if grid[dy][dx] == 0:
                queue.append((dy, dx))
                grid[dy][dx] = value + 1
 
# 0이 남아있을 경우 -1 출력 후 종료
max_value = 0
is_zero = False
for y in range(n):
    for x in range(m):
        if grid[y][x] == 0:
            is_zero = True
        max_value = max(max_value, grid[y][x])
# 최대값 - 1
 
if is_zero:
    print(-1)
else:
    print(max_value - 1)

코드 설명

1. 입력 처리

m, n = map(int, input().split())
grid: list[list[int]] = []
 
for _ in range(n):
    row = list(map(int, readline().split()))
    grid.append(row)
  • m: 가로 칸 수, n: 세로 칸 수
  • grid: 토마토 상태를 저장하는 2D 배열

2. 다중 시작점 큐 초기화

queue = deque([])
for y in range(n):
    for x in range(m):
        if grid[y][x] == 1:
            queue.append((y, x))
  • 모든 익은 토마토(값이 1인 위치)를 큐에 추가
  • 이렇게 하면 모든 익은 토마토에서 동시에 BFS가 시작됨

3. BFS 탐색

while queue:
    v = queue.popleft()
    value = grid[v[0]][v[1]]
    for d in offset:
        dy = v[0] + d[0]
        dx = v[1] + d[1]
 
        if 0 <= dy < n and 0 <= dx < m:
            if grid[dy][dx] == 0:
                queue.append((dy, dx))
                grid[dy][dx] = value + 1
  • 큐에서 위치를 꺼내고, 현재 위치의 값(일수)을 가져옴
  • 상하좌우 네 방향을 확인
  • 범위 체크 후, 익지 않은 토마토(0)를 발견하면 큐에 추가하고 일수를 저장
  • value + 1로 저장하여 하루씩 증가시킴

4. 결과 확인

max_value = 0
is_zero = False
for y in range(n):
    for x in range(m):
        if grid[y][x] == 0:
            is_zero = True
        max_value = max(max_value, grid[y][x])
 
if is_zero:
    print(-1)
else:
    print(max_value - 1)
  • 모든 칸을 확인하여 익지 않은 토마토(0)가 남아있는지 확인
  • 최대값을 찾아서 출력 (시작이 1이므로 -1을 해서 실제 일수 계산)

시간 복잡도

  • 시간 복잡도: O(N × M)

    • 모든 칸을 한 번씩 방문
    • 각 칸에서 상하좌우 확인은 상수 시간

  • 공간 복잡도: O(N × M)

    • 그리드 저장: O(N × M)
    • 큐: 최악의 경우 O(N × M)

풀이 포인트

1. 다중 시작점 처리

단일 시작점이 아닌 여러 시작점을 동시에 큐에 넣어야 합니다. 이렇게 하면 각 위치까지의 최소 일수를 올바르게 계산할 수 있습니다.

2. 거리 저장 방식

그리드에 직접 일수를 저장하는 방식을 사용합니다:

  • 시작점: 1
  • 1일 후: 2
  • 2일 후: 3
  • …

최종 결과는 max_value - 1입니다.

3. 익지 않은 토마토 확인

BFS가 끝난 후에도 값이 0인 칸이 남아있다면, 그 토마토는 익을 수 없는 위치입니다.

관련 문제

그래프 뷰

백링크