[python3] 백준 1039 (교환, BFS)

 

N값으로 값이 주어지는 경우 i 번째와 j 번째를 바꾸어 새로운 수를 만든다. 이때 K번 연산을 하여 나올 수 있는 최댓값을 구하면 된다.
N값은 1,000,000으로 값이 커보이지만 문자열 연산을 하기 때문에 긴 값은 아니다.
K값 또한 10으로 시간 복잡도상으로 큰 값이 아니다.

만약 2133이 존재할때

i=0, j=2로 하는 경우 3123이 된다.

i=0,j=3로 하는 경우 3132이 된다.

그렇다면 2133을 1번 변환하여 만들수 있는 최댓값은 3132이다. 

그러나 2133을 2번 변환하여 만들수 있는 값이 3321인데 3132로는 3321을 만들수 없다.

즉 K-1번의 결과값이 K번의 결과 값과는 상관이 없다.

 

따라서 모든 경우의 수를 탐색해야 K번 연산 했을때의 최댓값을 구할 수 있다.

그렇다면 완전탐색을 해야하는데 BFS를 사용하여 해당 값의 최댓값을 구할 수 있다. 그러나 중복이 존재할 수 있기 때문에 중복을 제거하기 위해 set을 사용해서 중복을 제거하면서 BFS를 K번만큼 진행하면 문제를 해결할 수 있다.

"""
데이터가 작고 K가 10 이하이므로
완탐으로 풀린다. 따라서 BFS로 매번 모든 경우를 찾고 해당 값 중에 가장 큰것을 선택하여 갱신
매번 최대를 구하는게 아니라 K번실행하는 경우의 최댓값을 구해야한다.
"""
from collections import deque

N, K = map(int, input().split())


def BFS(k, start):

    q = deque([start])
    count = 0

    while q:
        if count == k:  # K번 진행한 경우 해당 값들중에 최댓값을 반환한다.
            return max(q)
        setq = set()
        for _ in range(len(q)):
            target = q.popleft()
            target = list(str(target))
            for i in range(len(str(start))):
                for j in range(i+1, len(str(start))):
                    tmp = list(target)
                    tmp[i] = target[j]
                    tmp[j] = target[i]  # i,j값을 교환한다.
                    if tmp[0] == '0':  # 앞자리가 0인경우 값을 저장하지 않는다
                        continue
                    setq.add(int("".join(tmp)))  # set에 다음에 나올 수 있는 값을 저장한다.
        q += (list(setq))
        count += 1


tmp = BFS(K, N)
if tmp == None:
    print(-1)
else:
    print(tmp)