[BOJ/백준] 16985 Maaaaaaaaaze 파이썬

문제 링크 : https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

이동 조건을 잘못이해해서 헤맸던 문제이다. 입구에서 이동할 때 바깥 면에 있는 칸으로만 이동이 된다고 이해해서 예제 입력 3번부터 답이 이상했다. 근데 알고보니 그냥 3차원 BFS 바깥면 상관없이다 모든 칸으로 이동이 가능한거였다.

 

문제는 순열+배열회전+BFS인데 크게 어려운건 없다고 생각했다.

 

주어진 판의 순서를 섞고 각 판을 회전하여 조합을 만든 후 BFS로 최단거리를 구하면 되는 문제이다.

판 섞는 것은 itertools의 permutations 메소드로 아주 편하게 생성했다.

0~4까지 숫자에서 5개를 가지고 순열을 생성하여 order에 저장했고, 꼭대기는 몇번 판, 그 밑은 몇번판 이런식으로 저장된다.

 

이후 order 순서대로 배열을 회전하였다.

회전은 tmp 배열 하나 만들어서 거기에 원본 값 넣고 끝에부터 회전하여 원본배열에 다시 저장했다.

그림처럼 tmp의 row를 원본 배열의 col으로 넣어주면 된다.

인덱스만 잘 조절하면 돼서 어렵지 않게 할 수 있다.

tmp[x][y]를 원본[y][4-x]에 넣어주면 된다.

 

5번째 판까지 회전을 했다면 BFS를 돌리면 된다.

BFS는 3차원 공간에서하는 평범한 BFS이지만 시작 위치를 잘 조정해야한다.

그치만 이마져도 [0,0,0]에서 시작 [4,4,4]에서 끝 으로 하면 된다.

어차피 시작과 끝 판을 회전하면 모든 경우를 다 볼 수 있기 때문에 하나로 고정해도 된다.

 

from sys import stdin
from itertools import permutations
from collections import deque

input = stdin.readline
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
dz = [0,0,0,0,-1,1]
INF = 9876543210

board = [[list(map(int, input().split())) for _ in range(5)] for _ in range(5)]
visited = [[[0] * 5 for _ in range(5)] for _ in range(5)]
visited_num = 0
answer = INF

def solv():
    for order in permutations(range(5),5):
        stack_board(order,0)
    print(answer if answer != INF else -1)
def stack_board(order,idx):
    global board
    if answer == 12:
        return
    if idx == 5:
        simul(order)
        return
    for _ in range(4):
        board_rotate(order[idx])
        stack_board(order,idx+1)

def simul(order):
    global answer,visited,visited_num
    game_board = []
    for idx in order:
        game_board.append(board[idx])

    visited_num += 1

    start = [0,0,0]
    end = [4,4,4]

    if game_board[start[0]][start[1]][start[2]] != 1 or game_board[end[0]][end[1]][end[2]] != 1:
        return

    visited_num += 1
    q = deque([start+[0]])
    visited[0][start[0]][start[1]] = visited_num
    while q:
        z,x,y,cnt = q.pop()

        if cnt >= answer:
            continue
        if end[0] == z and end[1] == x and end[2] == y:
            answer = min(answer,cnt)
            break

        for d in range(6):

            nz = z + dz[d]
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nz,nx,ny,game_board):
                visited[nz][nx][ny] = visited_num
                q.appendleft((nz,nx,ny,cnt+1))
def point_validator(z,x,y,game_board):
    if z < 0 or x < 0 or y < 0 or z >= 5 or x >= 5 or y >= 5:
        return False
    elif game_board[z][x][y] == 0:
        return False
    elif visited[z][x][y] == visited_num:
        return False
    return True

def board_rotate(z):
    global board

    tmp = []
    for row in board[z]:
        tmp_row = []
        for num in row:
            tmp_row.append(num)
        tmp.append(tmp_row)

    for x in range(5):
        for y in range(5):
            board[z][y][4-x] = tmp[x][y]

solv()