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
  • 네이버 블로그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기