백준_python 7576번 토마토 (그래프, BFS)

 

 

<문제 링크>

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

 

 

<정답 코드>

import sys
from collections import deque
 
input = sys.stdin.readline
 
def bfs(m, n, ground):
    directions = [(-1,0),(1,0),(0,-1),(0,1)]    # 동서남북 방향벡터 정의
    
    # 토마토 위치 = bfs 시작할 위치 저장
    q = deque([(i, j) for i in range(m) for j in range(n) if ground[i][j] == 1])
    
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and ground[nx][ny] == 0:
                ground[nx][ny] = ground[x][y] + 1
                q.append((nx, ny))
    
def calculate_days(m, n, ground):
    bfs(m, n, ground)
 
    max_days = 0
    
    # 모든 셀이 업데이트 되었는지 확인
    for row in ground:
        for v in row:
            if v == 0:
                return -1
            max_days = max(max_days, v)
    return max_days - 1
 
n, m = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(m)]
 
result = calculate_days(m, n, ground)
print(result)

 

ground 배열 값 변화

 

처음에 DFS로 시도했는데, 토마토가 익어가는건 깊이 우선이 아니라 너비 우선이기 때문에 BFS로 풀어야 한다.

복잡한 문제로 보이지만, BFS를 이해하고 차근차근 풀면 이해할 수 있는 문제였다.