코딩하는 해맑은 거북이
[Python] 토마토(2) - 백준 (BFS) 본문
해당 글은 백준 7569번 문제 '토마토'을 다룬다.
문제
https://www.acmicpc.net/problem/7569
설명
이전에 풀었던 토마토 백준 문제에서 높이가 추가된 확장문제이다.
이전에 풀었던 BFS 처럼 dh만 추가하여 6가지 방향을 만들면 바로 해결할 수 있다.
코드
from collections import deque
c, r, h = map(int, input().split())
boxes = []
for _ in range(h):
box = []
for _ in range(r):
box.append(list(map(int, input().split())))
boxes.append(box)
dh = [-1, 1, 0, 0, 0, 0]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, 1, -1]
q = deque()
def bfs():
while q:
z, x, y = q.popleft()
for i in range(6):
nz = z + dh[i]
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < r and ny >= 0 and ny < c and nz >= 0 and nz < h:
if boxes[nz][nx][ny] == 0:
boxes[nz][nx][ny] = boxes[z][x][y] + 1
q.append((nz, nx, ny))
for i in range(h):
for j in range(r):
for k in range(c):
if boxes[i][j][k] == 1:
q.append((i, j, k))
bfs()
zero_count = 0
max_count = 0
for i in range(h):
for j in range(r):
for k in range(c):
if boxes[i][j][k] == 0:
zero_count += 1
max_count = max(max_count, boxes[i][j][k])
if zero_count == 0:
print(max_count-1)
else:
print(-1)
'코딩테스트' 카테고리의 다른 글
[Python] 치킨 배달 - 백준 (0) | 2023.08.13 |
---|---|
[Python] 나이순 정렬 - 백준 (0) | 2023.08.13 |
[Python] 적록색약 - 백준 (BFS) (0) | 2023.08.12 |
[Python] 토마토 - 백준 (BFS) (0) | 2023.08.11 |
[Python] 그림 - 백준 (DFS) (0) | 2023.08.11 |
Comments