1039.교환

테스트 코드는 모두 통과했으나 , 반례를 못찾아서 풀지 못한 문제다..

# 무조건 k번 수행해야 함
# input : n, k / output : k번 바꾸어 나올 수 있는 최댓값
n, k = input().split()

number = list(n)
k = int(k)

# 자릿수가 1자리이거나, 뒷자리에 0만 포함되어 있을 시
if len(number) == 1 or set(number) == {number[0], '0'}:
    result = -1
    print(result)

else:
    idx = 0
    # 1~i 내림차순 진행
    # i~k 내림차순으로 정렬되어 있을 경우, 남은 횟수(k-i)만큼 가장 작은 두 수끼리 교환
    while (idx < len(number)-1) and (k > 0):
        max_idx = idx
        max_num = number[idx]
        for j in range(idx+1, len(number)):
            # 최댓값 찾기
            if number[j] >= max_num:
                max_num = number[j]
                max_idx = j

        if max_idx == idx:
            if idx < len(number) - 1:
                idx += 1
        else:
            # 최댓값과 자리 바꾸기
            number[idx], number[max_idx] = number[max_idx] , number[idx]
            k -= 1
            idx += 1
    
    if k > 0 and k%2 == 1:
        number[-1], number[-2] = number[-2], number[-1]
    
    result = int(''.join(number))
    print(result)

무조건 내림차순으로 정렬해야 하는것이 아니라, k번 내로 어떤 경로로든 자리 간 변경을 하면서 k번 변경했을 시 나올 수 있는 최댓값을 구해야 하는 문제이므로 이 접근법은 잘못되었다.

# 교환
from collections import deque
N, K = map(int, input().split())
M = len(str(N))


def bfs(N, K):
    visited = set()
    visited.add((N, 0))
    q = deque()
    q.append((N, 0))
    answer = 0
    while q:
        n, k = q.popleft()
        if k == K:
            answer = max(answer, n)
            continue
        n = list(str(n))
        for i in range(M-1):
            for j in range(i+1, M):
                if i == 0 and n[j] == '0':
                    continue
                n[i], n[j] = n[j], n[i]
                nn = int(''.join(n))
                if (nn, k+1) not in visited:
                    q.append((nn, k+1))
                    visited.add((nn, k+1))
                n[i], n[j] = n[j], n[i]
    return answer if answer else -1


print(bfs(N, K))

k번 변경했을 때의 모든 경우의 수를 BFS 방법으로 접근하여, k == K 일 때 최댓값을 갖는 Answer를 출력하는 코드이다.