[BFS] 백준 7569번 : 토마토 / 골드 5

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

7569번: 토마토

import collections
m, n, h = map(int, input().split())

box = []
left = 0
q = collections.deque()

for z in range(h):
    table = []
    for y in range(n):
         row = list(map(int, input().split()))
         for x in range(len(row)):
             if row[x] == 0:
                 left += 1
             if row[x] == 1:
                 q.append([x, y, z])
         table.append(row)
    box.append(table)

def spread(i, j, k):
    ripe = 0
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz = [0,0,0,0,-1,1]

    for d in range(6):
        nx = i + dx[d]
        ny = j + dy[d]
        nz = k + dz[d]
        if 0<=nx<m and 0<=ny<n and 0<=nz<h and box[nz][ny][nx] == 0:
            box[nz][ny][nx] = 1
            q.append([nx, ny, nz])
            ripe += 1
    return ripe

day = 0
if not q:
    print(-1)
    quit()

if left == 0:
    print(0)
    quit()


while q:
    day += 1
    ripe = 0
    for _ in range(len(q)):
        i, j, k = q.popleft()
        ripe += spread(i, j, k)

    left -= ripe
    if left == 0:
        break

    if not q:
        print(-1)
        quit()
print(day)

처음엔 bfs 생각을 아예 못하고 브루트 포스로 접근했다.

전수 탐색을 하면서 1이 있으면 주변 조사, 임시로 2로 -> 다시 전수 탐색하면서 2면 1로 변경

이러니 시간 초과 발생.

시간을 줄일 방법은 더 이상 없는 것 같아 질문 목록을 참고했는데 bfs로 접근했다는 글을 보고

다시 생각해봤다.

 

bfs로 q를 유지하면서 원소를 하나씩 빼면서 그 주변을 조사.

이때 전 방법보다 훨씬 좋은 점은 전수탐색을 2번하지 않아도 된다는 것.