[백준 7576] 토마토 (Gold 5)

문제

요약

익은 토마토의 상하좌우 방향에 있는 익지 않은 토마토는 하루 뒤에 익은 토마토가 된다.
모든 익지 않은 토마토가 익은 토마토가 되는 데 걸리는 최소 일수를 구하자.
만약 토마토가 모두 익지 못하는 상황이면 -1을 출력하자.

풀이

1. BFS

맨 처음에, 큐에 1의 좌표들을 넣는다.
만약 격자에 0이 없다면 탐색을 시작할 필요가 없고, cnt 0 을 출력하면 된다.
큐에 있는 좌표들의 상하좌우를 탐색하면서 0들을 찾아 1 로 바꾸고, 예비 큐에 넣는다.
원래 큐에 있던 모든 요소들을 pop 하면, 예비 큐를 원래 큐로 복사해온다.
이 과정을 반복한다.
탐색하지 못한 0이 있는지 확인해준다.
결과를 출력한다.

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

m, n = map(int, input().split())
arr = [
    list(map(int, input().split())) for _ in range(n)
]

visit = [
    [True for _ in range(m)] for _ in range(n)
]

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

q = deque()

ex_zero = False

for r in range(n):
    for c in range(m):
        if arr[r][c] == 1:
            q.append([r, c])
        elif not ex_zero and arr[r][c] == 0:
            ex_zero = True

ans = 0
t = []
while q and ex_zero:
    y, x = q.popleft()
    visit[y][x] = False
    arr[y][x] = 1
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]

        if 0 <= ny < n and 0 <= nx < m and visit[ny][nx] and arr[ny][nx] == 0:
            visit[ny][nx] = False
            arr[ny][nx] = 1
            t.append([ny, nx])

    if not q and t:
        ans += 1
        q = deque(t)
        t = []


key = True

for i in range(n):
    for j in range(m):
        if visit[i][j] and arr[i][j] == 0:
            key = False
            break

print(ans if key else -1)

[백준 7576] 토마토 (Gold 5)

문제

요약

분류

풀이

1. BFS