24. 백준 1039 (골드2) : 교환_ python풀이 / BFS

문제

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을 출력한다.

예제 입력 1 복사

16375 1

예제 출력 1 복사

76315

예제 입력 2 복사

132 3

예제 출력 2 복사

312

예제 입력 3 복사

432 1

예제 출력 3 복사

423

예제 입력 4 복사

90 4

예제 출력 4 복사

-1

예제 입력 5 복사

5 2

예제 출력 5 복사

-1

예제 입력 6 복사

436659 2

예제 출력 6 복사

966354

---

*문제해석

K가 1일 경우는 0번째 자리 수와 가장 큰 자리 수를 바꾸면 되는 간단한 일이지만 K가 커질수록 점점 어려워 진다.

한 가지 방법은 모든 교환하는 경우를 만들어 원래 수와 비교해가며 가장 큰 값을 찾는 것이 될 것이다.

이를 위해 너비우선탐색 방법을 사용하기로 했고 큐에 모든 교환 결과를 집어 넣어줬으며 visited리스트를 통해 중복저장이 되는 것을 방지 했다.

 

마지막으로 K번 교환하는 경우의 수를 다 저장한 큐에서 하나씩 꺼내며 원래보다 큰 경우 그것으로 대체하면 될 것이다.

 

*나의 풀이

import sys
from collections import deque
input= sys.stdin.readline

def make_num():
	#문자열이된 N과 교환횟수K
    q = deque([[str(N), K]])
    visit = [[0]*1000001 for _ in range(K)]
    answer = -1
    
    
    while q:
        str_n, cnt = q.popleft()
        #K번 숫자 바꾸면
        if cnt == 0:
        	# 더 큰 값으로 갱신 후 다시 while문
            if answer < int(str_n): answer = int(str_n)
            continue
        #i와 j비교
        for i in range(len(str_n)-1):
            for j in range(i+1, len(str_n)):
                #0인 값은 바꿀이유가 없다
                if i == 0 and str_n[j] == '0':continue
                # 문자열 교환을 new_n에 집어넣는다
                new_n = str_n[:i] + str_n[j] + str_n[i+1:j] + str_n[i] + str_n[j+1:]
                # 만약 그 수를 방문하지 않았다면 큐에 그 수를 집어넣고 방문처리
                if not visit[cnt-1][int(new_n)]:
                    q.append([new_n, cnt-1])
                    visit[cnt-1][int(new_n)] = 1
    return answer

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

 

*정리

그동안 풀었던 DFS, BFS 문제는 그래프에서 풀었던 문제라 dx, dy를 먼저 설정한 경우가 많았다. 따라서 무조건 dx, dy가 있어야 하는 줄 알았지만 큐를 이용해 모든 경우를 저장하고 큐에서 뽑아 그것을 비교하는 식으로 푸는 것도 BFS(너비우선탐색)인 걸 깨달을 수 있던 좋은 문제라고 생각한다