이번 문제는 BFS, DFS, 배열 돌리기를 활용하여 해결하였다. BFS를 통해 입구에서 출구까지의 이동을 구현하였고, DFS를 통해 배열을 돌리는 모든 경우와 시작점과 끝점이 1일 경우에 BFS를 호출하는 로직을 구현하였고, zip 내장함수를 활용하여 배열 돌리기를 구현하였다. 막힘 없이 바로 입구에서 출구로 가는 방법의 최단 거리는 12이므로 만약 답 중에 12가 한번이라도 나온다면 바로 12를 답으로 하고 프로그램을 종료하도록 하였다.

Code

from itertools import permutations
from collections import deque
grid = [[list(map(int, input().split())) for _ in range(5)] for _ in range(5)]
tmp = [[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)]
dz, dy, dx = [0, 0, 1, 0, -1, 0], [0, 0, 0, 1, 0, -1], [1, -1, 0, 0, 0, 0]
answer = 1e9
def rotate_grid(lst):
    rotated = list(zip(*lst[::-1]))
    for i in range(5):
        rotated[i] = list(rotated[i])
    return rotated
def move(grid):
    global answer
    q = deque()
    q.append((0, 0, 0, 0))
    visited = [[[False for _ in range(5)] for _ in range(5)] for _ in range(5)]
    visited[0][0][0] = True
    while q:
        z, y, x, cnt = q.popleft()
        if (z, y, x) == (4, 4, 4):
            if cnt == 12:
                print(cnt)
                quit()
            answer = min(answer, cnt)
            return
        for i in range(6):
            nz, ny, nx = z+dz[i], y+dy[i], x+dx[i]
            if 0 <= nz < 5 and 0 <= ny < 5 and 0 <= nx < 5:
                if grid[nz][ny][nx] == 1 and not visited[nz][ny][nx]:
                    visited[nz][ny][nx] = True
                    q.append((nz, ny, nx, cnt+1))
def dfs(cur):
    if cur == 5:
        if tmp[4][4][4]:
            move(tmp)
        return
    for i in range(4):
        if tmp[0][0][0]:
            dfs(cur+1)
        tmp[cur] = rotate_grid(tmp[cur])
for i in permutations([0, 1, 2, 3, 4]):
    for j in range(5):
        tmp[i[j]] = grid[j]
    dfs(0)
if answer == 1e9:
    answer = -1
print(answer)