16985: Maaaaaaaaaze

문제 링크

16985: Maaaaaaaaaze

구현 방식

1. permutations를 이용해서 5층의 순서를 정해준다

2. 순서를 정한 후, dfs 탐색으로 하나의 판을 0도, 90도, 180도, 270도 회전해주고, 이 과정을 depth == 5가 될 때까지 반복하여 모든 층을 회전해준다 (4^5의 가짓수를 고려)

   • 반시계방향 90도 회전: list(reversed(list(map(list, zip(*A)))))

3. 2의 과정에서, depth가 5이고 시작점과 도착점이 모두 1인 경우에 bfs를 수행하여 최단 거리를 구해준다

코드

import sys
from collections import deque
from itertools import permutations

dx = (1, -1, 0, 0, 0, 0)
dy = (0, 0, 1, -1, 0, 0)
dz = (0, 0, 0, 0, 1, -1)

def bfs():
    global answer

    queue = deque([]); queue.append((0, 0, 0, 0))
    visit = [[[False for _ in range(5)] for _ in range(5)] for _ in range(5)]; visit[0][0][0] = True

    while queue:
        x, y, z, cnt = queue.popleft()
        if (x, y, z) == (4, 4, 4):
            answer = min(answer, cnt)

        for i in range(6):
            nx, ny, nz = x+dx[i], y+dy[i], z+dz[i]
            if 0<=nx<5 and 0<=ny<5 and 0<=nz<5:
                if not visit[nz][nx][ny] and miros[nz][nx][ny] == 1:
                    visit[nz][nx][ny] = True
                    queue.append((nx, ny, nz, cnt+1))

def dfs(depth): #미로 한판 돌리기
    if depth == 5:
        if miros[0][0][0] == 1 and miros[4][4][4] == 1:
            bfs()
        return
    for i in range(4): #미로 한판 돌리기 (0도, 90도, 180도, 270도)
        dfs(depth+1)
        miros[depth] = list(reversed(list(map(list, zip(*miros[depth])))))


boards = []; miros = [[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)]
for n in range(5):
    board = []
    for i in range(5):
        board.append(list(map(int, sys.stdin.readline()[:-1].split())))
    boards.append(board)

board_idx = [0, 1, 2, 3, 4]; answer = int(10e9)
for candi_idx in permutations(board_idx, 5): #층 순서 정하기
    for i in range(5):
        miros[candi_idx[i]] = boards[i]
    dfs(0)
if answer == int(10e9): print(-1)
else: print(answer)