[백준/파이썬] 7576번 토마토 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 7576번 토마토
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

익은 토마토(1)에서 인접한 안 익은 토마토(0)로 하루마다 전염이 진행됩니다.
모든 토마토가 익는 최소 날짜를 구하고, 끝까지 못 익는 토마토가 있으면 -1을 출력하는 문제입니다.

여러 시작점(처음부터 익은 토마토들)에서 동시에 퍼져나가므로,
멀티 소스 BFS로 푸는 전형 문제입니다.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

from collections import deque
from sys import stdin

m, n = map(int, input().split())
tomatos = [list(map(int, stdin.readline().split())) for _ in range(n)]

Q = deque([])
for i in range(n):
    for j in range(m):
        if tomatos[i][j] == 1:
            Q.append((i, j, 0))

days = 0
while Q:
    tmp = Q.popleft()
    if tmp[0] > 0 and tomatos[tmp[0]-1][tmp[1]] == 0:
        Q.append((tmp[0]-1, tmp[1], tmp[2]+1))
        tomatos[tmp[0]-1][tmp[1]] = 1
    if tmp[1] > 0 and tomatos[tmp[0]][tmp[1]-1] == 0:
        Q.append((tmp[0], tmp[1]-1, tmp[2]+1))
        tomatos[tmp[0]][tmp[1]-1] = 1
    if tmp[0] < n-1 and tomatos[tmp[0]+1][tmp[1]] == 0:
        Q.append((tmp[0]+1, tmp[1], tmp[2]+1))
        tomatos[tmp[0]+1][tmp[1]] = 1
    if tmp[1] < m-1 and tomatos[tmp[0]][tmp[1]+1] == 0:
        Q.append((tmp[0], tmp[1]+1, tmp[2]+1))
        tomatos[tmp[0]][tmp[1]+1] = 1
    days = tmp[2]

flag = True
for row in tomatos:
    for tomato in row:
        if tomato == 0:
            flag = False
            break
    if not flag:
        break
    
print(days if flag else -1)

설명

처음 익은 토마토를 큐에 전부 넣고 (행, 열, 날짜) 형태로 BFS를 수행합니다.

• 큐에서 하나를 꺼내 4방향 확인
• 안 익은 토마토(0)면 익힘 처리(1) + 날짜+1로 큐 삽입
• BFS 종료 후 0이 남아 있으면 -1, 없으면 마지막 날짜 출력

한 번 익힌 칸을 즉시 1로 바꿔 중복 방문을 막는 방식입니다.

---

• 백준 문제풀이 전체 목록 보기

---