BOJ 7576 토마토

https://www.acmicpc.net/problem/7576
시간 1초, 메모리 256MB
input :

• M N(2 ≤ M(가로), N(세로) ≤ 1,000)
• M개의 정수(1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어있지 않은 칸)

output :

• 토마토가 모두 익을 때까지의 최소 날짜를 출력(만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력)

조건 :

• 보관 후 하루가 지나면, 익은 토마토들의 상, 하, 좌, 우에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

---

BFS를 이용해서 토마토를 익게 하는데.
좌표 / 소요한 날짜를 인풋으로 준다.
토마토들이 다 익은 상황이라면 날짜의 변동이 없어 0이 출력되고 그렇지 않다면
날짜가 출력된다.

마지막에 이중반복문을 돌며 현재에 익지 않은 토마토가 있는지 확인 하고 그에 따른 출력을 한다.

import sys
from _collections import deque

m, n = map(int, sys.stdin.readline().split())
graph = []

for i in range(n):
    data = list(sys.stdin.readline().split())
    graph.append(data)
q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == '1':
            q.append((i, j, 0))

while q:
    x, y, day = q.popleft()
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= n or nx < 0 or ny >= m or ny < 0:
            continue
        if graph[nx][ny] == '0':
            graph[nx][ny] = '1'
            q.append((nx, ny, day + 1))

total = m * n
cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == '1':
            cnt += 1
        elif graph[i][j] == '-1':
            total -= 1
if cnt == total:
    print(day)
elif cnt < total:
    print(-1)