[백준 16985] Maaaaaaaaaze(Python 풀이)

풀이

이 문제는 브루트포스, 순열, BFS를 이용하여 풀어야한다.(이외에도 배열 회전 알고리즘 등 복잡한 문제이다.)

import sys
from collections import deque
from itertools import permutations

board = [[list(map(int, input().split(' '))) for _ in range(5)] for _ in range(5)]
b = [[[0] * 5 for _ in range(5)] for _ in range(5)]
result = sys.maxsize

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

다음과 같이 입력을 받고, result, dh, dy, dx를 다음과 같이 선언해둔다.

def solve():
    for d in permutations([0, 1, 2, 3, 4]):
        for i in range(5):
            b[d[i]] = board[i]
        dfs(0)

문제에서 참가자는 판을 5개 마음대로 쌓을 수 있다 -> 5개의 원소 중 5개를 나열하는 순열로 경우의 수를 구한다.
(5x4x3x2x1 총 120 개의 경우의 수 )
[0, 1, 2, 3, 4] 배열로 순열을 구한 후 인덱스를 이용하여 배열을 섞는다. 그리고 dfs() 함수를 불러 최소 길이를 구한다.

def rotate(b):
    # 배열의 90도 회전
    tmp = [[0] * 5 for _ in range(5)]
    for i in range(len(b)):
        for j in range(len(b[0])):
            tmp[j][4 - i] = b[i][j];

    return tmp


def dfs(d):
    # dfs를 이용한 완전 탐색
    global b
    if d == 5:
        if b[4][4][4]:
            bfs(b)
        return

    for i in range(4):
        if b[0][0][0]:
            dfs(d + 1)
        b[d] = rotate(b[d])

dfs() 함수에서는 배열을 90도씩 rotate하며 재귀함수를 요청한다. 만약 board의 시작 좌표(0, 0, 0)가 0인 경우는 출발이 불가능하므로 재귀함수를 호출하지 않는다.

d == 5, 즉 모든 판의 회전을 완료한 경우 bfs() 함수에서 최소 거리를 찾는다. 마찬가지로 종료 좌표(4, 4, 4)가 0인 경우에는 호출하지 않는다.

def bfs(b):
    global result
    q = deque()
    dist = [[[0, 0, 0, 0, 0] for _ in range(5)] for _ in range(5)]
    q.append((0, 0, 0))

    while q:
        h, y, x = q.popleft()
        if (h, y, x) == (4, 4, 4):
            result = min(result, dist[4][4][4])
            if result == 12: # 가장 짧은 경로의 경우 출력 후 종료
                print(result)
                exit()
            return

        for i in range(6):
            nh = h + dh[i]
            ny = y + dy[i]
            nx = x + dx[i]

            if nh < 0 or nh >= 5 or ny < 0 or ny >= 5 or nx < 0 or nx >= 5:
                continue
            elif b[nh][ny][nx] == 0 or dist[nh][ny][nx] != 0:
                continue
            q.append((nh, ny, nx))
            dist[nh][ny][nx] = dist[h][y][x] + 1

bfs() 함수에서는 시작(0, 0, 0) 부터 이동 가능한 좌표를 넓이 우선 탐색으로 찾아가며 dist 배열에 거리를 기록한다.
만약  종료좌표(4, 4, 4)에 도달하면 result에 최솟값을 저장한다.

이 때 result가 12라면 가장 짧은 경로 이므로 12를 출력하고 종료한다. (계속 시간초과가 났었는데 이것을 적용해서 문시간을 많이 줄였다.

 

전체 소스 코드

import sys
from collections import deque
from itertools import permutations

board = [[list(map(int, input().split(' '))) for _ in range(5)] for _ in range(5)]
b = [[[0] * 5 for _ in range(5)] for _ in range(5)]
result = sys.maxsize

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


def rotate(b):
    tmp = [[0] * 5 for _ in range(5)]
    for i in range(len(b)):
        for j in range(len(b[0])):
            tmp[j][4 - i] = b[i][j];

    return tmp


def bfs(b):
    global result
    q = deque()
    dist = [[[0, 0, 0, 0, 0] for _ in range(5)] for _ in range(5)]
    q.append((0, 0, 0))

    while q:
        h, y, x = q.popleft()
        if (h, y, x) == (4, 4, 4):
            result = min(result, dist[4][4][4])
            if result == 12: # 가장 짧은 경로의 경우 출력 후 종료
                print(result)
                exit()
            return

        for i in range(6):
            nh = h + dh[i]
            ny = y + dy[i]
            nx = x + dx[i]

            if nh < 0 or nh >= 5 or ny < 0 or ny >= 5 or nx < 0 or nx >= 5:
                continue
            elif b[nh][ny][nx] == 0 or dist[nh][ny][nx] != 0:
                continue
            q.append((nh, ny, nx))
            dist[nh][ny][nx] = dist[h][y][x] + 1


def dfs(d):
    global b
    if d == 5:
        if b[4][4][4]:
            bfs(b)
        return

    for i in range(4):
        if b[0][0][0]:
            dfs(d + 1)
        b[d] = rotate(b[d])


def solve():
    for d in permutations([0, 1, 2, 3, 4]):
        for i in range(5):
            b[d[i]] = board[i]
        dfs(0)


solve()

if result == sys.maxsize:
    result = -1
print(result)