[BOJ] 1327 - 소트 게임 (Python)

 

 

아이디어

 

BFS와 딕셔너리를 이용해 각 순열을 만드는 데 뒤집는 횟수를 구한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    N, K = map(int, input().split())
    number = list(map(int, input().split()))
    sorted_num = tuple(sorted(number))
    memo = dict()
    memo[tuple(number)] = 1
    queue = [number]
    while queue:
        _queue = []
        for num in queue:
            for i in range(N-K+1):
                temp = num[:]
                temp[i:i+K] = temp[i:i+K][::-1]
                if not memo.get(tuple(temp)):
                    memo[tuple(temp)] = memo[tuple(num)]+1
                    _queue.append(temp)
        queue = _queue
    print(memo.get(sorted_num, 0)-1)

solution()