[Python] 백준 7576 - 토마토 문제 풀이

Overview

BOJ 7576번 토마토 Python 문제 풀이
분류: Graph Traversal (그래프 탐색), bfs

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from collections import deque


def main():
    def input():
        return stdin.readline().rstrip()
    M, N = map(int, input().split())

    box = []
    cnt = 0
    riped = deque()
    for i in range(N):
        box.append(list(map(int, input().split())))
        for j in range(M):
            if box[i][j] == 0:
                cnt += 1
            elif box[i][j] == 1:
                riped.append((i, j, 1))
	
    # 탐색 방향 (상하좌우)
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    
    # bfs 탐색
    res = 0
    while cnt > 0 and riped:
        cy, cx, res = riped.popleft()

        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]

            if 0 <= ny < N and 0 <= nx < M and box[ny][nx] == 0:
                cnt -= 1
                riped.append((ny, nx, res + 1))
                box[ny][nx] = 1

    if not riped:
        res = -1
    print(res)


if __name__ == "__main__":
    main()

bfs를 응용한 탐색방법으로 익은 토마토와 덜 익은 토마토를 조사한다.
만약 익은 토마토의 상하좌우 위치에 덜익은 토마토가 있는 경우, deque에 해당 위치와 날짜를 저장한다. 그리고 deque에서 pop 될 때는 해당 토마토는 익은 토마토로 처리하고 이전 내용을 반복한다.
위 bfs 응용 탐색을 상자의 토마토가 모두 익거나 덜익은 토마토 만큼 반복하고, 결과를 출력한다.