[python] baekjoon 2549 : 루빅의 사각형

문제

-> 문제 링크 : https://www.acmicpc.net/problem/2549

2549번: 루빅의 사각형

 

문제풀이

입력값은 2차원 배열이지만 1차원 배열로 만들어 16자리의 수열을 정렬시키는 문제로 풀면 된다.

이때 숫자를 배열보다는 문자열로 만드는 게 딕셔너리를 사용할 때 시간이 적게 든다.

하지만 10을 넘는 숫자가 있어 2차원 배열에서의 자리를 유추하기가 힘들다. 모든 숫자가 한 글자가 되도록 16진수의 수로 바꿔 표현하면 1차원 배열의 자리를 보고 2차원 배열을 유추할 수 있게 된다.

 

BFS를 돌면서 현재 수열에서 행과 열을 돌리는 연산을 수행하여 만들어지는 수열을  만드는 작업을 반복하면 몇 번 만에 정렬된 수열을 만들 수 있는지 알 수 있다.

이때 처음 나오는 수열은 수열을 Key로하고, 이 수열이 어떤 수열에서 몇번째 칼럼이나 로우를 몇 번 돌려서 만들어졌는지에 대한 정보를 Value로 해서 Past라는 딕셔너리에 저장해둔다.

이 값은 BFS가 모두 끝난 후 최소 횟수가 어떤 연산으로 이루어졌는지 알기 위해 저장해놓는다.

 

문제는 일반 BFS로 돌리면 시간초과가 난다는 것이다. 그렇기 때문에 양방향 탐색을 사용해 구현해야 한다.

양방향 탐색이란 시작 수열과 정렬된 수열 두 곳에서 같이 BFS를 시작한다. 양쪽에서 시작한 두 경로가 서로 만난다면 그 경로가 시작 수열에서 정렬된 수열로 가는 최단 경로가 된다.

구현 과정에서는 시작 수열에서 시작한 BFS는 양수의 깊이를 갖고, 정렬된 수열에서 시작했으면 음수의 깊이를 갖는다.

만약 새로 만든 수열이 반대 부호의 깊이를 갖고 있다면 두 BFS가 만난 지점이라고 할 수 있다.

 

두 BFS가 만나면 Past 딕셔너리에 저장해둔 정보를 통해 어떤 연산을 통해 만들어졌는지 순서대로 뽑아낸다.

이때 주의할 점은 정렬된 수열에서 시작한 BFS에서 만들어진 수열들은 몇 번 돌렸는지에 대한 정보 k를 그대로 쓰지 않고 4-k를 쓴다.

이는 "123456789ABCDEFG"가 첫 번째 행을 한번 돌리면 "D23416785ABC9EFG"가 되는데

"D23416785ABC9EFG"를 "123456789ABCDEFG"로 만들려면 첫 번째 행을 세 번 돌리는 연산이 필요하다.

행이나 열을 한 방향으로밖에 돌릴 수 없어서 생기는 문제이다.

 

코드

import sys
from collections import deque

def changeRow(array, num):
    start = num * 4
    for i in range(4):
        array[start], array[start + i] = array[start + i], array[start]
    return array

def changeCol(array, num):
    for i in range(4):
        array[num], array[num + i * 4] = array[num + i * 4], array[num]
    return array

def bfs(start, finish):
    queue = deque()
    start = "".join(start)
    finish = "".join(finish)

    queue.append((finish, -1))
    queue.append((start, 1))

    past[start] = (1,None,None,None,None)
    past[finish] = (-1,None,None,None,None)

    while queue:
        now, level = queue.popleft()

        if level > 0:
            next_level = level + 1
        else:
            next_level = level - 1

        next = list(now)

        for idx, func in enumerate([changeRow, changeCol], start=1):

            for i in range(4):
                for k in range(4):
                    next = func(next, i)
                    key = "".join(next)

                    # 처음 발견한 수열이면 정보를 저장.
                    if past.get(key) is None:
                        past[key] = (next_level, now, idx, i+1, k+1) # parent, i, k
                        queue.append((key, next_level))

                    # 두 BFS가 만난다면(이미 발견한 수열인데 깊이의 부호가 다름) 최단 경로를 찾은 것이므로 리턴
                    else:
                        length = abs(past[key][0]) + abs(level) - 1
                        if (past[key][0] < 0 and level > 0) :
                            return now, (idx, i+1, k+1), key, length
                        elif (past[key][0] > 0 and level < 0) :
                            return key, (idx, i+1, 4-(k+1)), now, length

past = {}
square = []
finish = [str(i) for i in range(1, 17)]

for _ in range(4):
    square.extend(list(map(str, sys.stdin.readline().rstrip().split())))

# 10진수 -> 16진수
mapper = {str(i):chr(64+i) for i in range(1,17)}
finish = [mapper[num] for num in finish]
square = [mapper[num] for num in square]

start,center,end,length = bfs(square, finish)

print(length)
answer = []

# 시작 수열에서 시작한 BFS에서 나온 경로
while past.get(start) :
    level, next, rc, i, k = past[start]
    if next is not None :
        answer.append((rc, i, k))
        start = next
    else :
        break
answer = list(reversed(answer))

# 두 BFS가 만난 시점의 경로
answer.append((center[0], center[1], center[2]))

# 정렬된 수열에서 시작한 BFS에서 나온 경로
while past.get(end) :
    level, next, rc, i, k = past[end]
    if next is not None :
        answer.append((rc, i, 4-k))
        end = next
    else :
        break

for ans in answer :
    print(ans[0], ans[1], ans[2])

 

 

2코드에 잘못된 부분이나 개선 사항을 댓글로 알려주시면 감사하겠습니다.