[백준 - Python] 1039 - 교환

0.  문제 링크

 

 

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

1039번: 교환

---

1.  풀이 방법

 

 

1. 완전 탐색 비슷하게 풀었다. 참고로 BFS이다.
2. 다만 최대 10억 개를 탐색해야 하는데, 이렇게 하면 무조건 시간초과가 난다.
3. 최대 1,000,000의 길이이지만, 각 위치의 숫자는 0~9이다. 따라서 무조건 중복이 발생한다.
4. 그러므로 중복을 잘 체크한다면 빠르게 풀 수 있다.
5. BFS를 할 때는 실제로 자리를 바꿔줘서 해결하면 된다.

 *참고로 string끼리 대소비교 가능하다.

---

2.  코드

 

 

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


if __name__ == "__main__":
    n, k = input().split()
    n = list(n)
    k = int(k)
    l = len(n)

    if l == 1:      # 길이가 1이라면 교환을 못함
        print(-1)
        exit(0)

    ans = '0' * l

    check = set()
    dq = deque()
    dq.append((''.join(n), 0))

    while dq:
        num, cnt = dq.popleft()
        if cnt == k:
            ans = max(ans, num)     # cnt == k라면 대소비교를 해야함 -> 참고로 str도 대소비교 가능
        else:
            num = list(num)
            for i in range(l - 1):
                for j in range(i + 1, l):
                    if i == 0 and num[j] == '0':        # 앞자리 0 방지
                        continue

                    num[i], num[j] = num[j], num[i]     # 교환함

                    temp = ''.join(num)
                    if (temp, cnt + 1) not in check:        # 중복이 아니라면
                        check.add((temp, cnt + 1))
                        dq.append((temp, cnt + 1))

                    num[i], num[j] = num[j], num[i]     # 복구함

    print(-1 if ans == '0' * l else ans)        # 만약 ans를 업데이트하지 않았다면 -1을 출력함

---

3.  마무리