백준 7569 파이썬(BFS)

이 코드로 했더니 테스트케이스의 답들은 잘 나오는데

시간초과가 떠버렸다.

3차원 배열을 사용해야 하는 문제라서 반복문 3개를 썻다고 시간초과가 나오는 건 아닐거라고 생각한다.

 

확실한 이유는 아닐 수도 있지만

내 생각에 중간에 zip내장함수를 이용해서 좌표를 만들어낼때 내부적으로 연산이 더 되는게 아닌가 싶다.

사실 잘 모르겠다.

어떤 부분에서 시간 초과가 나는지...ㅠㅠ

# 7569 토마토 3차원 문제
import sys
input = sys.stdin.readline
m,n,h = map(int,input().split())
graph = [[] for _ in range(h)]
for i in range(h):
    for _ in range(n):
        graph[i].append(list(map(int,input().split())))
# graph[층h][가로m][세로n]

arrow = [[1,0,0],
         [-1,0,0],
         [0,-1,0],
         [0,1,0],
         [0,0,-1],
         [0,0,1]] # 상 하 좌 우 위 아래

from collections import deque
def bfs_tomato(m,n,h,graph,cnt=0):

    # 모든 토마토가 이미 채워져 있는 경우
    queue = deque()
    test = set()
    for z in range(h):
        for x in range(n):
            for y in range(m):
                if graph[z][x][y] == 1:
                    queue.append([z,x,y])
                test.add(graph[z][x][y])
    if 0 not in test:
        return 0

    while queue:
        cnt += 1
        for _ in range(len(queue)):
            tomato = queue.popleft()
            for i in arrow:
                new = [x+y for x,y in zip(tomato,i)]
                if new[0] < 0 or new[0] > h-1 or new[1] < 0 or new[1] > n-1 or new[2] < 0 or new[2] > m-1:
                    continue
                if graph[new[0]][new[1]][new[2]] == 0:
                    queue.append(new)
                    graph[new[0]][new[1]][new[2]] = 1
        # print(f'queue:{queue},count:{cnt}') 출력확인용
     
    for z in range(h):
        for x in range(n):
            for y in range(m):
                if not bool(graph[z][x][y]):
                    return -1
    return cnt-1

print(bfs_tomato(m,n,h,graph))

 

구글링한 코드중 제일 이해가 잘 되고 직관적이라고 생각한 것을 보고 이해했다.

내가 코드한것과 다른 부분은 실질적으로 bfs탐색과정중 상하좌우위아래를 탐색할때 리스트로 좌표를 받아서 탐색하는게 아니라 바로 탐색한다는것...

앞으로는 나도 저렇게 코딩해볼 수 있도록 안보고 몇번 더 연습해보는 시도를 해봐야겠다.

 

from collections import deque

def BFS():
    while Q:
        x,y,z = Q.popleft()

        for i in range(6):
            nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]

            if 0 <= nx < H and 0 <= ny < N and 0 <= nz < M:
                if arr[nx][ny][nz] == 0:
                    arr[nx][ny][nz] = arr[x][y][z] + 1
                    Q.append((nx,ny,nz))


M, N, H = map(int, input().split())
arr = [[] for _ in range(H)]
for i in range(H):
    for _ in range(N):
        arr[i].append(list(map(int, input().split())))

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

answer = 0
Q = deque()

for i in range(H):
    for j in range(N):
        for k in range(M):
            if arr[i][j][k] == 1:
                Q.append((i,j,k))

BFS()
Flag = False

for i in range(H):
    for j in range(N):
        for k in range(M):

            if arr[i][j][k] == 0:
                Flag = True
                break
            answer = max(answer, arr[i][j][k])

if Flag:
    answer = -1
elif answer == -1:
    answer = 0
else:
    answer -= 1

print(answer)