이번 문제는 BFS를 통해 해결하였다. 우선 2개의 인덱스 간의 수 교환이 필요하기 때문에 그 모든 경우를 itertools의 combinations을 통해 구해주었다. 그리고 k번 교환이 반복되었을 때의 최댓값을 구해야 하기 때문에 q에 넣을 때 교환 횟수를 세는 카운팅 변수를 같이 넣어 주었다. while문 안에서 q의 길이만큼 반복하는 for문을 통해 q의 모든 수를 빼내면 모든 수의 카운팅 변수는 같은 수를 가지게 된다. 카운팅 변수가 k보다 작을 경우에는 combinations를 통해 수를 모두 교환해주고, k와 같아지면 결과 변수를 최댓값으로 갱신해주고, k보다 커지면 k와 같을 때를 모두 확인한 것이므로 결과 변수를 반환하도록 하였다. 다음 수를 결정할 때에는 방문처리 집합을 통해 방문처리가 되어있지 않을 때에만 진행하도록 하였고, while문이 끝날 때까지 return되지 않으면 -1을 반환하도록 하였다.

Code

import itertools
from collections import deque
n, k = map(str, input().split())
k = int(k)
n = list(n)
methods = list(itertools.combinations([i for i in range(len(n))], 2))
def find_max():
    q = deque()
    q.append((n, 0))
    visited = set()
    visited.add((''.join(n), 0))
    result = 0
    while q:
        for i in range(len(q)):
            num, cnt = q.popleft()
            if cnt == k:
                result = max(result, int(''.join(num)))
            if cnt > k:
                return result
            for a, b in methods:
                nxt = num[:]
                if not (a == 0 and nxt[b] == '0'):
                    nxt[a], nxt[b] = nxt[b], nxt[a]
                    if (''.join(nxt), cnt+1) not in visited:
                        visited.add((''.join(nxt), cnt+1))
                        q.append((nxt, cnt+1))
    return -1
print(find_max())