[백준] 1327. 소트 게임 (Python)

📌 1327. 소트 게임

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

풀이과정

하나씩 확인하면서 뒤집어주고 다시 반복하면 될 것 같아서 다음과 같이 dfs로 풀었다.

n, k = map(int, input().split())

array = list(map(int, input().split()))

target = sorted(array)

answer = int(1e9)

def dfs(str, cnt):
  global n, k, target, answer
  #print(str)
  if str == target:
    answer = min(answer, cnt)
  if cnt > n*k:
    return
  for i in range(1, n-k+2):
    str2 = sorted(str[:i+k]) + str[i+k:]
    dfs(str2, cnt+1)


dfs(array, 0)
if answer == int(1e9):
  print(-1)
else:
  print(answer)

하지만 언제 break을 해주어야 하는지, visited 리스트는 어떻게 활용해야 하는지 감이 서지 않았다. 그래서 확실하지 않지만 느낌으로 n*k보다 답이 커질 때 멈추게 두었다.

어떻게 이문제를 해결해야 할까?

1. 언제 break을 해주어야 하는지 모르는 문제

bfs를 이용하면 너비 우선 탐색으로 가장 먼저 sort하게 나오면 그 횟수가 바로 정답이 될 것이다.

2. visited 리스트를 어떻게 활용해야 하는지에 대한 문제

visited 리스트를 False, True 를 담는 리스트가 아니라 set으로 둔다. (set이 아닌 리스트로 할시, 시간 초과가 발생한다)

💯 정답

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int, input().split())

array = list(input().split())
visited = set("".join(array))
#visited.add(array)

target = sorted(array)

answer = -1

q = deque([[array, 0]])

while q:
  arr, cnt = q.popleft()
  if arr == target:
    answer = cnt
    break
  for i in range(n-k+1):
    rarr = arr[i:i+k]
    rarr.reverse()
    arr2 = arr[:i] + rarr + arr[i+k:]
    str2 = "".join(arr2)
    if str2 not in visited:
      q.append([arr2, cnt+1])
      visited.add(str2) #set에 원소 추가

print(answer)

(수정 2023.03.03)

• set에는 리스트를 넣지 못한다. 따라서 string 형태로 바꾸어 줘야 함을 꼭 기억하자.
• join을 이용해서 리스트를 string 형태로 바꿀때에 리스트에 담겨있는 데이터가 int이면 안되고 string 형태여야 합칠 수 있다.