[BOJ] 7576. 토마토 (Python)

7576번: 토마토

 

오랜만에 보는 토마토 문제~!

정말 대표적인 BFS 문제라고 할 수 있다.

 

 

from collections import deque


def solution() :
    M, N = map(int, input().split())

    dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 이동 방향
    q = deque([])
    tomatoes = []
    for row in range(N) : 
        tomato = list(map(int, input().split()))
        for col in range(M) :
            if tomato[col] == 1 : # 처음 익은 토마토 위치 저장
                q.append((row, col))
        tomatoes.append(tomato)
    
    def check_pos(x, y) :
        if 0 <= x < N and 0 <= y < M :
            return True
        return False
        
    def bfs(q) :
        answer = -1
        while q :
            x, y = q.popleft()
            for i in range(4) :
                nx, ny = x + dxy[i][0], y + dxy[i][1]
                if check_pos(nx, ny) and tomatoes[nx][ny] == 0 : # 아직 안 익은 토마토가 있으면
                    tomatoes[nx][ny] = tomatoes[x][y] + 1
                    q.append((nx, ny))
                    answer = tomatoes[nx][ny]
        
        # 익지 못하는 토마토가 있는지 체크
        for i in range(N) :
            for j in range(M) :
                if tomatoes[i][j] == 0 :
                    return -1
        return answer -1
    
    answer = bfs(q)
    return answer

print(solution())