[python] 백준 1039 교환

https://www.acmicpc.net/problem/1039

1039번: 교환

문제 해결

• 숫자 안에 서로 다른 두개의 자릿수의 숫자를 바꿔가며 K번 바꾸었을 때 가장 큰 수를 만들 경우를 찾는 문제이다.
• 따라서 처음에 두 자릿수의 숫자를 바꿔서 가장 큰 수가 나왔다고 K번 바꾸었을 때 가장 큰 수가 만들어진다고 할 수 없다.
• 즉 거의 모든 경우의 수를 다 계산해야한다.
• 하지만 예외가 있다. 만약 한 자리의 자릿수가 가장 큰 자릿수, 즉 맨 왼쪽에 있는 수이고 나머지 하나의 자릿 수가 0일 경우 총 숫자의 자리수가 줄어들게 된다. 이런 경우는 예외의 경우라 해서 제외시킨다.
• 중복 계산을 피하기 위해 (수, 자릿수 바꾼 횟수)를 visited 집합을 통해 저장하여 중복되지 않도록 한다.
• K번 바꾸었으면 이전에 K번 바꾸었을 때 가장 컸던 숫자와 비교해서 더 커지면 저장하고 작아지면 버리는 식으로 비교한다.

 

CODE

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

def bfs(n:int, k:int):
    visited= set()
    visited.add((n,0))
    que = deque()
    que.append((n,0))
    answer = 0
    while que:
        now_n, now_k = que.popleft()
        if now_k == k:
            answer = max(answer,now_n)
            continue
        now_n = list(str(now_n))
        for i in range(m-1):
            for j in range(i+1,m):
                if i==0 and now_n[j] == '0':continue
                now_n[i], now_n[j] = now_n[j], now_n[i]
                x = int(''.join(now_n))
                if (x,now_k+1) not in visited:
                    que.append((x, now_k+1))
                    visited.add((x, now_k+1))
                now_n[i], now_n[j] = now_n[j], now_n[i]
    return answer if answer !=0 else -1

    
    

if __name__=='__main__':
    n, k = map(int, input().split())
    m = len(str(n))

    print(bfs(n,k))