백준 1039번 교환 파이썬 풀이

1. K번 할 수 없는 경우는?
   1. M이 1이하인 경우
   2. M에서 0인 자리수를 전부 뺐을 떄 1이하
      1. 라고 생각했는데, 사실 9000이면 0끼리 교환하면 되니까 틀린 조건. 2자리일 때 일의자리가 0인 경우이다.
2. BFS와 DFS의 핵심은 수형도에 있다.

정답풀이

#2022.06.08.00:01 - 00:43
from collections import deque
import sys
input = sys.stdin.readline

def main ():
    n,k = map(int,input().split())
    m = len(str(n))

    if m == 1 :
        print(-1)
        return

    if m==2 and n%10 ==0:
        print(-1)
        return

    def swap(cur, i,j):
        # 12345 1,3 -> 14325
        curStr = str(cur)
        return int(curStr[:i]+curStr[j]+curStr[i+1:j]+curStr[i]+curStr[j+1:])


    # BFS
    cur_k = 0
    q= deque()
    q.append(n)

    while(q and cur_k<k):
        v= set()
        for _ in range(len(q)):
            cur = q.popleft()
            # print('cur:',cur)
            for i in range(len(str(cur))):
                for j in range(i+1,len(str(cur))):
                    res = swap(cur,i,j)
                    if res not in v:
                        v.add(res)
                        q.append(res)
            # print(cur_k, v,q)
        if cur_k == k-1:
            print(max(v))





        cur_k+=1



    return


main()