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

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

1327번: 소트 게임

---

문제

---

풀이

0. 방향성 생각

• visit에 뒤집은 배열들을 문자열 형태로 변환해서 방문처리한다.
•  

1. 입력

from collections import deque

n,k = map(int,input().split())
arr = input().split()
visit = set()
goal = sorted(arr)

 

2. 뒤집기 함수 정의

def flip(array,x):
    temp = array[:]
    temp[x-1:x-1+k] = temp[x-1:x-1+k][::-1]
    return temp

 

3. 출력

q = deque([(arr,0)])
while q:
    a,t = q.popleft()
    if a == goal:
        print(t)
        break

    for i in range(n-k+1):
        na = flip(a,i+1)
        na_str = ''.join(na)
        if na_str not in visit:
            q.append((na,t+1))
            visit.add(''.join(na))
else:
    print(-1)

• 바꿀 수 있는 모든 경우의 수를 탐색한다.
• 방문하지 않은 경우는 큐에 추가하고, 문자열로 변환하여 visit에 추가한다.

---

전체코드

from collections import deque

n,k = map(int,input().split())
arr = input().split()
visit = set()
goal = sorted(arr)

def flip(array,x):
    temp = array[:]
    temp[x-1:x-1+k] = temp[x-1:x-1+k][::-1]
    return temp


q = deque([(arr,0)])
while q:
    a,t = q.popleft()
    if a == goal:
        print(t)
        break

    for i in range(n-k+1):
        na = flip(a,i+1)
        na_str = ''.join(na)
        if na_str not in visit:
            q.append((na,t+1))
            visit.add(''.join(na))
else:
    print(-1)

코멘트

백준 1525 퍼즐이랑 비슷함