[백준 BOJ / Python] 1327번 소트 게임

문제

1부터 N까지의 정수로 이루어진 순열을 오름차순으로 정렬할 때, 최소 몇 번의 뒤집기를 해야 하는지 구하는 문제이다.

정렬은 특정 위치 iii에서 시작하여 오른쪽으로 K개의 숫자를 뒤집는 연산을 반복하는 방식으로 이루어진다. 

예를 들어 N이 5, K가 3일 때, (5, 4, 3, 2, 1) 순열이 주어진 경우

1. i=0에서 뒤집으면 (3, 4, 5, 2, 1) 이 된다.
2. i=1에서 뒤집으면 (3, 2, 5, 4, 1) 이 된다.
3. i=2에서 뒤집으면 (3, 2, 1, 4, 5) 이 된다.
4. i=0에서 뒤집으면 (1, 2, 3, 4, 5) 이 되면서 정렬이 완료된다.

최소 4번의 뒤집기로 오름차순 순열을 만들 수 있다.

풀이

• 이 문제는 각 순열 상태를 노드로 보고, 한 번의 뒤집기로 다른 상태로 이동하는 최단 경로 탐색 문제로 볼 수 있다.
• 그렇기 때문에 BFS를 사용해 정렬된 상태로 도달하는 최소 횟수를 구할 수 있다.
• 먼저 큐에 최초로 입력된 순열과 뒤집기 횟수(0)를 저장한다.
• 최소 뒤집기 횟수를 구할 수 있는 BFS 알고리즘을 수행한다.
  • 현재 순열이 정렬된 순열인지 확인하고, 정렬이 완료되었다면 뒤집은 횟수를 출력한다.
  • 현재 순열에서 가능한 모든 뒤집기를 시도해 새로운 순열을 생성한다. (0 ≤ i ≤ N-K)
  • 만약 새로운 순열이 이전에 만들었던/방문했던 순열이 아니라면 큐에 추가하고 visited에 추가해 방문 표시를 한다.

Python 코드

from collections import deque
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
seq = tuple(map(int,input().split()))

q = deque([(seq, 0)])
visited = set()
while q:
    cur, d = q.popleft()

    if cur == tuple(range(1,n+1)):
        print(d)
        break

    for i in range(n-k+1):
        next_seq = cur[:i]+cur[i:i+k][::-1]+cur[i+k:]
        if next_seq not in visited:
            visited.add(next_seq)
            q.append((next_seq, d+1))
else:
    print(-1)

 

문제출처

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