백준 1039 교환 (파이썬)

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

1039번: 교환

1. 입력의 자릿수에 대해 2개씩 조합할 수 있는 경우를 구해놓는다

2. 자릿수를 K번째 까지 계속 바꾼 후 만들 수 있는 가장 큰 수를 출력한다

   만약 ans 값이 초기값인 0 그대로면 만들 수 없다는 뜻이므로 -1 출력

from collections import deque
from itertools import combinations
import sys, copy

input = sys.stdin.readline

def bfs():
    c = set()
    ans = 0
    qlen = len(q)
    while qlen:
        x = q.popleft()
        l = list(str(x))
        for i, j in d:
            s = copy.deepcopy(l)
            temp_i, temp_j = s[i], s[j]
            s[i], s[j] = temp_j, temp_i
            if s[0] == '0':
                continue
            nx = int(''.join(s))
            if nx not in c:
                ans = max(ans, nx)
                c.add(nx)
                q.append(nx)
        qlen -= 1
    return ans

n, k = map(int, input().split())
item = [i for i in range(len(str(n)))]
d = list(combinations(item, 2))
q = deque()
q.append(n)

ans = 0
while k:
    ans = bfs()
    k -= 1
if not ans:
    print(-1)
else:
    print(ans)