백준 1327 소트 게임

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

k칸만큼 뒤집어 bfs를 통하여 원하는 정답의 최단거리를 찾는 문제이다.
방문배열을 어떻게 만들것인가가 문제인데, 만약 배열로 생성한다면 8^8만큼 크기의 배열을 생성해야 한다.
그렇기 때문에 공간 낭비가 심하고, 방문배열을 딕셔너리를 이용해 생성해주면 최대 8!(40320)만큼의 크기만 사용하므로 딕셔너리를 사용했을시 이점이 생긴다.

from collections import deque
n,k = map(int,input().split())
state = list(map(int,input().split()))
visited = {}
ascending = ''.join(map(str,list(range(1,n+1))))
visited[''.join(map(str,state))] = 0
queue = deque([])
queue.append((state,0))
ans = -1
while queue:
    next_state,cnt = queue.popleft()
    x = ''.join(map(str,next_state))
    if x == ascending:
        ans = cnt
        break
    for i in range(n-k+1):
        copystate = next_state[:]
        for j in range(k//2):
            copystate[i+j], copystate[i+k-j-1] = copystate[i+k-j-1], copystate[i+j]
        copystate_str = ''.join(map(str,copystate))
        if copystate_str not in visited:
            visited[copystate_str] = cnt + 1
            queue.append((copystate,cnt+1))
        else:
            visited[copystate_str] = min(visited[copystate_str], cnt+1)
print(ans)