BFS에서 벽 세우기(#7569 토마토)

BFS 너비우선탐색과 백준 #1012 유기농 배추, #7576 토마토
요 글의 토마토 문제에 대한 새로운 접근방안

BFS는 노드를 pop할 때마다 인근 노드들을 무지성으로 queue에 집어넣는다. 그렇게 모든 노드를 방문하게 된다.

그런데 그 중간중간에 분기점을 만들어야 하는 경우가 있다.

#7569 토마토
#5427 불
위 두 문제 같은 경우 문제에서 제시하는 작업이 종료되는데까지 며칠 / 몇 초가 걸리는지를 알아내야 하기 때문에, 하루 / 1초가 지날 때마다 이를 알 수 있어야 한다.

저번에 문제를 풀 때는 이를 위해 큐 두 개를 사용했다.
두 개의 큐를 bfs함수의 인자로 받아서 첫번째 큐에 들어있는 노드를 pop하고, 그때마다 첫번째 큐가 아닌 두번째 큐에 인접 노드를 추가했다. 첫번째 큐가 비면 함수 종료. 그럼 cnt를 증가시킨다. 이때 두번째 큐에는 다음 카운트에 pop해야 할 노드들이 들어있게 된다. 이 두번째 큐(두번째 인자로 들어왔던 큐)는 다음 bfs에서 첫번째 인자가 된다.

새로운 접근 방식은 bfs while문 내에서 for문을 사용하는 것이다.
while queue는 동일하되 while문 내에서 큐의 길이 만큼 for문을 돌려 노드를 pop하고, for문이 종료되면 cnt를 증가시킨다. 그럼 큐에는 이전 cnt에서 새롭게 추가된 노드들만 들어있게 된다. 그럼 또 이 길이만큼 for문을 돌려 pop. 이를 큐가 완전히 빌 때까지 무한 반복!

from collections import deque as dq
import sys

C,R,H = [int(i) for i in sys.stdin.readline().split()]
graph = []
queue = dq()
cnt = 0

dr=[0,0,0,0,-1,1]
dc=[0,0,-1,1,0,0]
dh=[1,-1,0,0,0,0]

for i in range(H):
	tmp = []
	for j in range(R):
		tmp.append(list(map(int, sys.stdin.readline().split())))
		for k in range(C):
			 if tmp[j][k]==1:
				 queue.append((i,j,k))
	graph.append(tmp)		

while queue:
	lev = len(queue)
	updated = False
	for _ in range(lev):
		h,r,c=queue.popleft()
		for i in range(6):
			nh=h+dh[i]
			nr=r+dr[i]
			nc=c+dc[i]
			if 0<=nr<R and 0<=nc<C and 0<=nh<H:
				if graph[nh][nr][nc]==0:
					graph[nh][nr][nc]=1
					queue.append((nh,nr,nc))
					updated = True
	if updated:
		cnt+=1

for i in range(H):
	for j in range(R):
		for k in range(C):
			if graph[i][j][k]==0:
				cnt = -1
				
print(cnt)