[골드 4] 백준 1327 - 소트 게임 (파이썬)

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

풀이

• 배열 A를 K개의 연속된 수만큼 뒤집는 연산을 통해 오름차순 [1, 2, ..., N]을 만드는 최소 횟수를 구하는 문제다.
• 상태공간이 최대 N!이므로, 모든 경우를 다 탐색하면 안 되고, BFS로 최소 횟수를 탐색해야 한다.
• 리스트 상태를 hash 값으로 바꿔서 방문 여부를 체크한다.

def list_to_hash(a):
    hash = 0
    for i in range(len(a)):
        hash += a[i]
        hash *= (len(a) + 1)
    return hash

• 리스트를 정수형 hash 값으로 변환.(다만 완전한 유일성 보장은 안 됨 → tuple(a)을 쓰는 것이 더 안전)
• 단순한 방식이지만, 충돌 가능성이 낮은 편이므로 작동에 문제는 없다.

visit = set()
dist = {}
queue = deque()

queue.append(A)
h_s = list_to_hash(A)
visit.add(h_s)
dist[h_s] = 0

• BFS 시작 - 초기 리스트 A를 큐에 넣고 방문 처리 및 거리 초기화.

while len(queue) != 0:
    a = queue.popleft()
    h_a = list_to_hash(a)

    for i in range(N - K + 1):
        b = a[:i] + a[i:i + K][::-1] + a[i + K:]
        h_b = list_to_hash(b)
        if h_b not in visit:
            queue.append(b)
            visit.add(h_b)
            dist[h_b] = dist[h_a] + 1

• 현재 리스트에서 가능한 모든 K길이 구간을 뒤집음.
• 방문하지 않은 상태면 큐에 추가 + 거리 기록.

h_t = list_to_hash(list(range(1, N + 1)))
if h_t in dist:
    print(dist[h_t])
else:
    print(-1)

• 정렬된 리스트 상태가 BFS 결과에 포함되어 있으면 그 때까지의 거리 출력.
• 아니면 -1 출력.

코드

# 백준 1327 - 소토 게임
# 분류 : BFS

from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))

def list_to_hash(a) :
    hash = 0
    for i in range(len(a)) :
        hash += a[i]
        hash *= (len(a) + 1)
    return hash

visit = set()
dist = {}
queue = deque()

queue.append(A)
h_s = list_to_hash(A)
visit.add(h_s)
dist[h_s] = 0

while len(queue) != 0 :
    a = queue.popleft()
    h_a = list_to_hash(a)

    for i in range(N - K + 1) :
        b = a[:i] +a[i:i + K][::-1] + a[i + K:]
        h_b = list_to_hash(b)
        if h_b not in visit :
            queue.append(b)
            visit.add(h_b)
            dist[h_b] = dist[h_a] + 1

h_t = list_to_hash(list(range(1, N + 1)))
if h_t in dist :
    print(dist[h_t])
else :
    print(-1)