728x90
3차원 BFS 문제였다.
어려운 문제는 아니었으나, 완숙한 토마토가 여러개인 상황에서 시작할 경우, 완숙한 토마토 array를 만들어서 큐에 넣고 bfs를 시작해야 한다는 것을 놓쳤었다.
C, R, H = map(int, input().split())
tomatoes = [[list(map(int, input().split())) for x in range(R)] for y in range(H)]
visited = [[[0]*C for x in range(R)] for y in range(H)]
from collections import deque
delta = [(0,1,0), (0,-1,0), (1,0,0), (-1,0,0), (0,0,1), (0,0,-1)]
def bfs(arr):
global res, visited, tomatoes
q = deque(arr)
for a in arr:
visited[a[0]][a[1]][a[2]] = 1
while q:
ch, cr, cc, cd = q.popleft()
if cd > res:
res = cd
for dr,dc,dh in delta:
nr = cr + dr
nc = cc + dc
nh = ch + dh
if 0 <= nr < R and 0 <= nc < C and 0 <= nh < H and not visited[nh][nr][nc] and tomatoes[nh][nr][nc] == 0:
q.append((nh, nr, nc, cd+1))
tomatoes[nh][nr][nc] = 1
visited[nh][nr][nc] = 1
return
res = 0
arr = []
for h in range(H):
for r in range(R):
for c in range(C):
# 1을 찾으면 바로 bfs를 시작하는게 아니라 1을 모두 다 찾은 뒤에 한꺼번에 큐에 넣고 탐색을 시작해야 한다.
if tomatoes[h][r][c] == 1:
arr.append((h, r, c, 0))
bfs(arr)
for h in range(H):
for r in range(R):
for c in range(C):
if tomatoes[h][r][c] == 0:
res = -1
break
print(res)
'''
반례
완숙한 토마토(1)가 여러개라면 그걸 모두 다 큐에 넣고 시작해야 한다
5 3 1
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
'''
'PS > Python' 카테고리의 다른 글
[Programmers] 모의고사 (0) | 2021.09.18 |
---|---|
[BOJ_Python] 2644. 촌수계산 (0) | 2021.04.17 |
[BOJ_Python] 1991. 트리 순회 (0) | 2021.04.08 |
[BOJ_Python] 14499. 주사위 굴리기 (0) | 2021.04.05 |
[BOJ_Python] 14500. 테트로미노 (0) | 2021.04.05 |
최근댓글