[BOJ/백준] 1039 교환 파이썬

문제 링크 : https://www.acmicpc.net/problem/1039

1039번: 교환

BFS로 풀었다.

처음에는 숫자는 최대 값이 1백만이고 k는 10이어서 1백만x11개의 배열을 만들어서 BFS로 풀이 했다.

큐에 쌓이는 것과 2천만크기의 배열때문에 메모리 초과가 난 것 같다.

 

그래서 방문 체크를 set을 사용했다.

대충 횟수 따져보자

입력이 123456이 들어오면 경우의 수는 6! 이므로 충분히 작다. 따라서 set으로 방문체크해도 충분히 통과할 수 있을 것 이다.

 

입력 숫자부터 각 숫자를 바꿔가면서 BFS를 진행하자.

방문 체크는 숫자+횟수로 했다. 같은 숫자라도 몇번 변경했느냐에 따라 정답으로 도출이 될 수 있기 때문에 방문 횟수도 체크줘야한다.

그래서 숫자+횟수로 방문 체크를 하고 값을 set에  저장하자.

 

마지막으로 변경횟수가 k 였을 때 최대값을 저장해서 답을 도출하자.

 

from collections import deque

n,k = input().strip().split()
size = len(n)
n,k = map(int, [n,k])

def solv():
    answer = 0
    visited = set()

    q = deque([(n,0)])
    while q:
        now,cnt = q.pop()
        if cnt == k:
            answer = max(answer, now)
            continue

        arr = list(map(int, str(now)))
        for i in range(size-1):
            for j in range(i+1,size):
                if i == 0 and arr[j] == 0: continue
                arr[i],arr[j] = arr[j],arr[i]
                num = list_to_int(arr)
                if num+cnt+1 not in visited:
                    q.appendleft((num,cnt+1))
                    visited.add(num+cnt+1)
                arr[i],arr[j] = arr[j],arr[i]
    print(answer if answer > 0 else -1)
def list_to_int(arr):
    result = 0
    for num in arr:
        result = result*10+num
    return result
solv()