[Python/파이썬] 백준 16985번 Maaaaaaaaaze

16985번: Maaaaaaaaaze

 

코드

from collections import deque
from itertools import permutations

boards = [[list(map(int, input().split())) for _ in range(5)]
          for _ in range(5)]
ans = 126


def rotate(board):  # 판을 시계 방향 회전
    new_board = [[0]*5 for _ in range(5)]
    for i in range(5):
        for j in range(5):
            new_board[j][4-i] = board[i][j]
    return new_board


def bfs(cube):  # 경로 탐색
    global ans
    q = deque([(0, 0, 0, 0)])
    dist = [[[False]*5 for _ in range(5)] for _ in range(5)]
    dist[0][0][0] = True

    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, -1, 1, 0, 0]
    dz = [0, 0, 0, 0, -1, 1]
    while q:
        x, y, z, cnt = q.popleft()
        if cnt > ans:
            return
        if x == 4 and y == 4 and z == 4:
            ans = min(ans, cnt)
            if cnt == 12:
                print(cnt)
                exit()
            return
        for d in range(6):
            nx = x+dx[d]
            ny = y+dy[d]
            nz = z+dz[d]
            if 0 <= nx < 5 and 0 <= ny < 5 and 0 <= nz < 5 and not dist[nx][ny][nz] and cube[nx][ny][nz] == 1:
                q.append((nx, ny, nz, cnt+1))
                dist[nx][ny][nz] = True
    return


def dfs(cube, idx): # 각 판의 회전
    if idx == 5:
        if cube[0][0][0] and cube[4][4][4]:
            bfs(cube)
        return
    for _ in range(4):
        dfs(cube, idx+1)
        cube[idx] = rotate(cube[idx])


for comb in permutations(range(5)): # 판 순서
    cube = []
    for i in comb:
        cube.append(boards[i])
    dfs(cube, 0)
print(ans if ans <= 125 else -1)

 

주어지는 입력은 5×5 판 5개로 확실히 안되는 경우들을 중간에 가지쳐내며 브루트포스로 풀이한다.

 

1. 5개의 판 순서 정하기 : 순열

itertools 라이브러리의 permutations 함수를 이용하여 입력으로 받은 5개의 판의 순서를 정하고, 이 판들을 각각 얼마나 돌려서 사용할지 정할 DFS함수를 호출한다.

 

2. 각 판의 회전 : DFS

5×5 판을 시계 방향으로 90도 회전시키는 rotate 함수를 이용하여 각 판을 회전시킨 후 다음 층으로 넘어가도록 dfs() 재귀호출. 이를 통해 모든 층의 판을 각각 회전시킬 수 있음.

❗ 큐브를 완성하고 BFS를 호출할 때(idx==5일 때), cube[0][0][0]==0 이거나 cube[4][4][4]==0인 경우는 BFS를 수행하지 않아도 이미 안되는 큐브이므로 이런 경우는 쳐낸다.

 

3. 길 찾기 : BFS

판 순서 배열, 각 판 회전한 결과물인 5×5×5 큐브에서 (0, 0, 0)에서 (4, 4, 4)로 가는 최단 경로 찾기.

❗ (0, 0, 0)에서 (4, 4, 4)로 가는 최단 경로는 모든 칸이 방문 가능한 경우에도 12이므로 (4, 4, 4)에 도달했을 때 cnt가 12일 경우에는 더이상 진행하지 않아도 된다. 그러므로 이때는 12를 출력하고 exit()한다.

 

❗로 표시한 경우들을 처리해주지 않으면 시간초과가 발생하므로 모두 처리를 해서 최대한 시간을 줄여야 한다.