[Python/파이썬] 백준 1039번 교환

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

코드

from collections import deque, defaultdict

n, k = input().split()
n_len = len(n)
k = int(k)

q = deque([(n, 0)])
visited = defaultdict(set)
visited[n].add(0)
answer = -1
while q:
    now, cnt = q.popleft()
    if cnt == k:
        answer = max(int(now), answer)
        continue
    for i in range(n_len-1):
        for j in range(i+1, n_len):
            if (i == 0 and now[j] == '0'):
                continue
            new_num = now[:i]+now[j]+now[i+1:j]+now[i]+now[j+1:]
            if (new_num not in visited or cnt+1 not in visited[new_num]) and cnt < k:
                q.append((new_num, cnt+1))
                visited[new_num].add(cnt+1)
print(answer)

 

문제의 조건을 살펴보면 입력값의 범위가 별로 크지 않은 것을 볼 수 있다. N은 1,000,000 이하의 자연수이고 K는 10 이하의 자연수이다. 그렇기 때문에 이 문제는 너비우선탐색과 같은 방법으로도 접근해볼 수 있다.

 

너비우선탐색의 구현은 간단하다. deque에서 뽑은 값에서 문제에 맞게 두 수의 위치를 바꾼 수를 다시 deque에 넣어가며 이 연산이 k번 됐을 때의 최대값을 구하면 된다.

 

다만 BFS는 deque에 정답까지 도달하며 사용되는 값들을 모두 넣기 때문에 메모리 초과를 조심해야 한다. 그래서 여기서도 이미 나왔던 값인지 확인하는 visited를 사용했는데, 단순히 N에서 순서를 바꾸고 있는 그 값만 visited에 기억해두면 안된다. 왜냐하면 N이 321이고 K가 2회인 경우에는 312로 바뀌었다가 321로 다시 바뀌는 경우도 가능해야 하기 때문이다.

이 때문에 visited를 딕셔너리 형태로 만들고 key를 N에서 순서를 바꾼 숫자값, value를 숫자를 바꾼 횟수의 집합이 되도록 했다. 예를 들면, 321에서 1번 변형하여 312가 됐다면 `visited["312"].add(1)` 이렇게 말이다.