7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
import sys
from collections import deque
sys.setrecursionlimit(10003)
if __name__ == '__main__':
M, N, H = map(int, sys.stdin.readline().rstrip().split())
graph = []
well_tomato_q = deque()
all_well_flag = True
for i in range(H):
temp = []
for j in range(N):
tomatos = list(map(int, sys.stdin.readline().rstrip().split()))
for k in range(len(tomatos)):
if tomatos[k] == 1:
well_tomato_q.append((i, j, k))
elif tomatos[k] == 0:
all_well_flag = False
temp.append(tomatos)
graph.append(temp)
def bfs(graph, q):
direction = [(0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1), (1, 0, 0), (-1, 0, 0)]
max_day = 0
while q:
now_h, now_n, now_m = q.popleft()
for d in direction:
nh = now_h + d[0]
nn = now_n + d[1]
nm = now_m + d[2]
if nh < 0 or nh >= H or nn < 0 or nn >= N or nm < 0 or nm >= M:
continue
if graph[nh][nn][nm] == 0:
graph[nh][nn][nm] = graph[now_h][now_n][now_m] + 1
max_day = max(max_day, graph[nh][nn][nm])
q.append((nh, nn, nm))
for i in graph:
for j in i:
if 0 in j:
return -1
return max_day - 1
if all_well_flag:
print(0)
else:
print(bfs(graph, well_tomato_q))
BFS로 풀었다.
3차원 배열이라 처음 입력받을때 약간 신경쓴것과 (1, 0, 0) 과 (-1, 0, 0) 두방향이 추가된것 말고는 이전에 풀었던 토마토 문제와 별 다를것 없었다.
very easy~