[백준] 7569 토마토

www.acmicpc.net/problem/7569

7569번: 토마토

 

이번엔 3차원배열이다. 2차원 배열에서 z축이 하나 더 생겼지만, 6개만 확인하면 되는 문제이므로 난이도가 확 올라가진 않는다.

여러번 시도했으나 지난 토마토 문제와 같이 시간초과가 떴다.

그래서 pypy로 확인해 보니 정답. 알고리즘엔 문제가 없는걸 확인했다.

다음은 pypy에서 돌아간 코드이다

from collections import deque

dz = [0, 0, 0, 0, -1, 1]
dy = [0, 0, -1, 1, 0, 0]
dx = [-1, 1, 0, 0, 0, 0]

m, n, h = map(int, input().split())
tomato = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
q = deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k] == 1:
                q.append((i, j, k))

tmp_q = deque()
count = 0
while q:
    dh, dr, dc = q.popleft()
    for i in range(6):
        if dh + dz[i] < 0 or dh + dz[i] >= h: continue
        if dr + dy[i] < 0 or dr + dy[i] >= n: continue
        if dc + dx[i] < 0 or dc + dx[i] >= m: continue
        if tomato[dh + dz[i]][dr + dy[i]][dc + dx[i]] == 0:
            tomato[dh + dz[i]][dr + dy[i]][dc + dx[i]] = 1
            tmp_q.append((dh + dz[i], dr + dy[i], dc + dx[i]))
    if not q:
        if not tmp_q: break
        q = tmp_q
        count += 1
        tmp_q = deque()

break_chk = False
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k] == 0:
                break_chk = True
                break
        if break_chk:
            break
    if break_chk:
        break
if break_chk:
    print(-1)
else:
    print(count)

하지만 기본 python 인터프리터 에서도 돌리고 싶은 욕구가 있어서 계속 도전을 해보았는데 계속 시간초과가 떴다.

그래서 이번엔 포기해야겠다고 생각하고 다른 사람의 코드를 봤는데 함수를 구현해서 사용한 사람들은 대부분 성공하는걸 확인했다.

나도 bfs와 break_chk 하는 부분을 함수로 만들어서 돌렸고 성공하였다

from collections import deque
from sys import stdin
input = stdin.readline

m, n, h = map(int, input().split())
tomato = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
q = deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k] == 1:
                q.append((i, j, k))

count = 0
def bfs(array, queue):
    global count
    tmp_q = deque()
    dz = [0, 0, 0, 0, -1, 1]
    dy = [0, 0, -1, 1, 0, 0]
    dx = [-1, 1, 0, 0, 0, 0]
    while queue:
        dh, dr, dc = queue.popleft()
        for i in range(6):
            if dh + dz[i] < 0 or dh + dz[i] >= h: continue
            if dr + dy[i] < 0 or dr + dy[i] >= n: continue
            if dc + dx[i] < 0 or dc + dx[i] >= m: continue
            if array[dh + dz[i]][dr + dy[i]][dc + dx[i]] == 0:
                array[dh + dz[i]][dr + dy[i]][dc + dx[i]] = 1
                tmp_q.append((dh + dz[i], dr + dy[i], dc + dx[i]))
        if not queue:
            if not tmp_q: return
            queue = tmp_q
            count += 1
            tmp_q = deque()


def break_chk(_list):
    for i in range(len(_list)):
        for j in range(len(_list[0])):
            for k in range(len(_list[0][0])):
                if tomato[i][j][k] == 0:
                    return True
    return False


bfs(tomato, q)
if break_chk(tomato):
    print(-1)
else:
    print(count)

앞으로는 재귀든 반복문이든 함수로 구현해야겠다.