boj7569 - 토마토(3차원)

문제

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

코드(4724ms)

import sys
input = sys.stdin.readline
from collections import deque
# 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토

col, row, height = map(int, input().split())
graph = [[list(map(int, input().split())) for _ in range(row)] for _ in range(height)]
# print(len(graph))

q = deque()
for k in range(height):
    for i in range(row):
        for j in range(col):
                if graph[k][i][j] == 1:
                    q.append([k,i,j])

dx = [0,0,1,-1]
dy = [1,-1,0,0]
dh = [1,-1]
def bfs():
    while q:
        h,x,y = q.popleft()
        for i in range(4):
            tx = x+dx[i]
            ty = y+dy[i]
            if 0<=tx<row and 0<=ty<col and graph[h][tx][ty] == 0: # 같은 층의 앞,뒤,왼,오
                q.append([h,tx,ty])
                graph[h][tx][ty] = graph[h][x][y] +1
            for hi in range(2):
                th = h+dh[hi] # 위, 아래 체크
                if 0<=th<height and graph[th][x][y] == 0:
                    q.append([th,x,y])
                    graph[th][x][y] = graph[h][x][y] +1
bfs()
# print(graph)

chk = False
ans = -1
for k in range(height):
    for i in range(row):
        for j in range(col):
            if graph[k][i][j] == 0:
                chk = True
            ans = max(ans, graph[k][i][j])

if chk:
    print(-1)
else:
    print(ans-1)

설명

3차원 그래프 bfs이기때문에 높이(h)까지 위, 아래로 바꾸어가며 탐색,
내 코드는 while문 안에 for문 두개라 총 8번 돌지만
steps = [[-1, 0, 0],[1, 0, 0],[0, -1, 0],[0, 1, 0],[0, 0, -1],[0, 0, 1]]
로 하면 그냥 6번 돌수 있음

steps = [[-1, 0, 0],[1, 0, 0],[0, -1, 0],[0, 1, 0],[0, 0, -1],[0, 0, 1]]
/////
for step in steps:
	th = h+step[0]
    	tx = x+step[1]
    	ty = y+step[2]
        if 0<=tx<row and 0<=ty<col and 0<=th<height and graph[th][tx][ty] == 0:
            q.append([th,tx,ty])
                graph[th][tx][ty] = graph[h][x][y] +1