[백준 🥇2] 16985번 Maaaaaaaaaze (Python/파이썬)

1️⃣ 문제

https://www.acmicpc.net/problem/16985

2️⃣ 코드

브루트포스와 BFS를 이용하여 풀었다

from itertools import permutations
from collections import deque
import sys

# 입력 받는 부분
maze = []
for i in range(5):
    temp = []
    for j in range(5):
        temp.append(list(map(int, sys.stdin.readline().split())))
    maze.append(temp)

dy = [0, 0, -1, 1, 0, 0]
dx = [-1, 1, 0, 0, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
    
answer = 5 ** 4

# 시계방향으로 90도 돌리기
def rotate(arr):
    result = [[0] * 5 for _ in range(5)]

    for r in range(5):
        for c in range(5):
            result[c][4-r] = arr[r][c]

    return result


# 입구에서 출구로 도달하는 최단 경로 찾기 
def bfs(temp):
    result = 5 ** 4

    if temp[0][0][0] == 1 and temp[4][4][4] == 1:
        q = deque()
        q.append([0, 0, 0])
        visited = [[[-1] * 5 for _ in range(5)] for _ in range(5)]
        visited[0][0][0] = 0

        while q:
            z, y, x = q.popleft()
            
            if z == 4 and y == 4 and x == 4:
                result = min(result, visited[z][y][x])
                break

            for i in range(6):
                nz = z + dz[i]
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= nz < 5 and 0 <= ny < 5 and 0 <= nx < 5:
                    if visited[nz][ny][nx] == -1 and temp[nz][ny][nx] == 1:
                        visited[nz][ny][nx] = visited[z][y][x] + 1
                        q.append([nz, ny, nx])

    return result
                        
            
# 미로 만드는 모든 경우 구하기
for p in list(permutations([0, 1, 2, 3, 4], 5)):
    temp = [maze[p[0]], maze[p[1]], maze[p[2]], maze[p[3]], maze[p[4]]]

    for a in range(4):
        temp[0] = rotate(temp[0])
        for b in range(4):
            temp[1] = rotate(temp[1])
            for c in range(4):
                temp[2] = rotate(temp[2])
                for d in range(4):
                    temp[3] = rotate(temp[3])
                    for e in range(4):
                        temp[4] = rotate(temp[4])

                        answer = min(answer, bfs(temp))


if answer == 5 ** 4:
    print(-1)
else:
    print(answer)

3️⃣ 풀이

미로판 쌓기는 순열 라이브러리를 이용하였고 회전은 무식하게 5중 for문을 이용하였다ㅎ
5개의 미로판을 각각 0도, 90도, 180도, 270도 회전할 수 있으므로 경우의 수는 4x4x4x4x4 → 5중 for문 사용해야했다
​

또 헷갈렸던 부분이
"큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸"이라는 내용이었다
첨엔 이 내용 때문에 아래 코드와 같이 8개의 꼭짓점 각각을 시작점으로 BFS를 돌리는 코드로 짰더니 시간초과가 떴었다

### ❌시간초과 코드❌ ###
from itertools import permutations
from collections import deque
import sys

maze = []
for i in range(5):
    temp = []
    for j in range(5):
        temp.append(list(map(int, sys.stdin.readline().split())))
    maze.append(temp)

start = [[0, 0, 0], [0, 0, 4], [0, 4, 0], [0, 4, 4],
         [4, 0, 0], [4, 0, 4], [4, 4, 0], [4, 4, 4]]
end = [[4, 4, 4], [4, 4, 0], [4, 0, 4], [4, 0, 0],
       [0, 4, 4], [0, 4, 0], [0, 0, 4], [0, 0, 0]]
dy = [0, 0, -1, 1, 0, 0]
dx = [-1, 1, 0, 0, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
    
answer = 5 ** 4


def rotate(arr):
    result = [[0] * 5 for _ in range(5)]

    for r in range(5):
        for c in range(5):
            result[c][4-r] = arr[r][c]

    return result


def bfs(temp):
    result = 5 ** 4
    
    for k in range(8):
        sz, sy, sx = start[k][0], start[k][1], start[k][2]   # 시작점 
        ez, ey, ex = end[k][0], end[k][1], end[k][2]  # 끝점 

        if temp[sz][sy][sx] == 1 and temp[ez][ey][ex] == 1:
            q = deque()
            q.append([sz, sy, sx])
            visited = [[[-1] * 5 for _ in range(5)] for _ in range(5)]
            visited[sz][sy][sx] = 0

            while q:
                z, y, x = q.popleft()

                if z == ez and y == ey and x == ex:
                    result = min(result, visited[z][y][x])
                    break

                for i in range(6):
                    nz = z + dz[i]
                    ny = y + dy[i]
                    nx = x + dx[i]
                    if 0 <= nz < 5 and 0 <= ny < 5 and 0 <= nx < 5:
                        if visited[nz][ny][nx] == -1 and temp[nz][ny][nx] == 1:
                            visited[nz][ny][nx] = visited[z][y][x] + 1
                            q.append([nz, ny, nx])

    return result
                        
            
for p in list(permutations([0, 1, 2, 3, 4], 5)):
    temp = [maze[p[0]], maze[p[1]], maze[p[2]], maze[p[3]], maze[p[4]]]

    for a in range(4):
        temp[0] = rotate(temp[0])
        for b in range(4):
            temp[1] = rotate(temp[1])
            for c in range(4):
                temp[2] = rotate(temp[2])
                for d in range(4):
                    temp[3] = rotate(temp[3])
                    for e in range(4):
                        temp[4] = rotate(temp[4])

                        answer = min(answer, bfs(temp))

if answer == 5 ** 4:
    print(-1)
else:
    print(answer)

하지만 회전+쌓기의 모든 경우를 이미 고려해주기 때문에 굳이 8개의 시작점에 대해 또 고려해줄 필요가 없었다
그니까 회전+쌓기의 경우들 속에 한가지 큐브 모양에 대해 8개의 입구로 시작하는 경우가 모두 포함된다

제출결과 pypy로만 통과
나중에 시간 더 줄이는 방법을 알게되면 업데이트 해야겠당