[백준/Python] 7576번 : 토마토

문제

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

7576번: 토마토

---

풀이

너비 우선 탐색을 이용하여 구현한다.
최소 날짜를 저장할 cnt, 안 익은 토마토 수를 저장할 zero, 익은 토마토의 위치를 저장할 q를 정의한다.
이중 반복문을 통해 익은 토마토라면 q에 append 하고, 안 익은 토마토의 개수를 확인한다.
만약 안 익은 토마토가 없다면 0을 출력한다.
만약 안 익은 토마토가 있다면 dfs를 수행한다.
 - q가 빌 때까지 반복한다.
 - 익은 토마토의 위치가 저장된 q에서 popleft 한 값의 인접한 네 곳의 위치를 (nx, ny)에 저장한다.
 - (nx, ny)의 값이 범위를 벗어나지 않고 해당 위치의 값이 0이라면,
 - q에 (nx, ny)를 append 하고, (nx, ny)에 popleft 한 값 + 1을 저장한다.
 - 앞에서 저장한 값이 날짜가 되므로 cnt를 갱신하고, 안 익은 토마토의 수(zero)를 -1 한다.
- 안 익은 토마토가 남아있다면 -1을 출력하고, 없다면 cnt-1을 출력한다. 

---

코드

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
board = [[*map(int, input().split())] for _ in range(m)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
cnt, zero = 0, 0
q= deque([])
for i in range(m):
    for j in range(n):
        if board[i][j] == 1:
            q.append((i, j))
        if board[i][j] == 0:
            zero += 1

if zero == 0:
    print(0)
else:
    while q:
        i, j = q.popleft()
        for k in range(4):
            nx, ny = i + dx[k], j + dy[k]
            if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 0:
                q.append((nx, ny))
                board[nx][ny] = board[i][j] + 1
                cnt = board[nx][ny]
                zero -= 1

    print(-1 if zero != 0 else cnt-1)