Set

[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번 연산 했을때의 최댓값을 구할 수 있다. 그렇다..