[백준/BOJ] gold3 - 1039번 교환 (Python)

▶1039 - 교환

백준 로고

▶문제

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

 

▶입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

 

▶출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

728x90

▶풀이

visit는 set으로 설정해 주었고, 그 안에는  num과 cnt를 넣어주었다.

해당 숫자가 다른 cnt에서 다시 나올 수도 있기 때문에 그렇게 설정해 주었다.

 

그 외에는 별다른 특이점이 없는 bfs 문제이다.

모든 i, j를 방문하면서 조건을 입력해 주면 충분히 풀 수 있는 문제이다.

from collections import deque


def bfs():
    queue = deque()
    queue.append((n, 0))
    visit = set()
    answer = []

    while queue:
        number, cnt = queue.popleft()
        if cnt == k:
            answer.append(number)
            continue
        
        string = list(str(number))
        for i in range(l):
            for j in range(i + 1, l):
                if i == 0 and string[j] == '0':
                    continue
                string[i], string[j] = string[j], string[i]
                num = int(''.join(string))
                if (num, cnt + 1) not in visit:
                    visit.add((num, cnt + 1))
                    queue.append((num, cnt + 1))
                string[i], string[j] = string[j], string[i]
    return answer


n, k = map(int, input().split())
l = len(str(n))

answer = bfs()
if len(answer) == 0:
    print(-1)
else:
    print(max(answer))