백준 7569 [토마토] 파이썬

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

7569번: 토마토

# 백준 7569
from collections import deque
import sys
dr = [0, 1, -1, 0, 0, 0]
dc = [1, 0, 0, -1, 0, 0]
dh = [0, 0, 0, 0, 1, -1]
input = sys.stdin.readline
M, N, H = map(int, input().split())
field = [[[0]*(M) for _ in range(N)] for _ in range(H)]
tomatos = []
for k in range(H):
    for j in range(N):
        s = list(map(int, input().split()))
        for i in range(M):
            if s[i] == 1:
                tomatos.append([k, j, i])
            field[k][j][i] = s[i]


def bfs(tomatos):
    q = deque([])
    for tomato in tomatos:
        q.append(tomato)
    while q:
        pos = q.popleft()
        for i in range(6):
            m = pos[2]+dc[i]
            n = pos[1]+dr[i]
            h = pos[0]+dh[i]
            if 0 <= m < M and 0 <= n < N and 0 <= h < H and field[h][n][m] != -1 and (field[h][n][m] == 0 or field[h][n][m] > 1+field[pos[0]][pos[1]][pos[2]]):
                field[h][n][m] = 1+field[pos[0]][pos[1]][pos[2]]
                q.append([h, n, m])


bfs(tomatos)
answer = 0
check = 0
for k in range(H):
    for j in range(N):
        for i in range(M):
            if field[k][j][i] == 0:
                check = 1
                break
            else:
                answer = max(answer, field[k][j][i])
        if check == 1:
            break
    if check == 1:
        break
if check == 1:
    print(-1)
else:
    print(answer-1)

bfs를 사용하여 해결하였다. (3차원 배열 접근 -->  arr[높이][세로][가로] 임을 기억하자!)

(pypy3로 해결하였습니다. python3 에서는 시간초과)

 

# 백준 7569 python3 통과
from collections import deque
import sys
dr = [0, 1, -1, 0, 0, 0]
dc = [1, 0, 0, -1, 0, 0]
dh = [0, 0, 0, 0, 1, -1]
input = sys.stdin.readline
M, N, H = map(int, input().split())
field = [[[0]*(M) for _ in range(N)] for _ in range(H)]
tomatos = []
for k in range(H):
    for j in range(N):
        s = list(map(int, input().split()))
        for i in range(M):
            if s[i] == 1:
                tomatos.append([k, j, i])
            field[k][j][i] = s[i]


def bfs(tomatos):
    q = deque([])
    for tomato in tomatos:
        q.append(tomato)
    while q:
        pos = q.popleft()
        for i in range(6):
            m = pos[2]+dc[i]
            n = pos[1]+dr[i]
            h = pos[0]+dh[i]
            if 0 <= m < M and 0 <= n < N and 0 <= h < H and field[h][n][m] != -1 and field[h][n][m] == 0:
                field[h][n][m] = 1+field[pos[0]][pos[1]][pos[2]]
                q.append([h, n, m])


bfs(tomatos)
answer = 0
check = 0
for k in range(H):
    for j in range(N):
        for i in range(M):
            if field[k][j][i] == 0:
                check = 1
            answer = max(answer, field[k][j][i])
if check == 1:
    print(-1)
else:
    print(answer-1)

상자의 위치 값이 0이라면(방문하지 않았다면) 값을 더하면 되므로, 값을 비교하는 연산은 필요가 없다.

(python3 통과)

--> 조그만한 시간차이도 중요하다!