[BOJ] 백준 1039번 문제 풀이 (Python)

1. 문제 풀이

BFS를 사용하여 중복 숫자를 만들지 않는 방식으로 시간을 단축하여 문제를 풀었습니다.

문제를 풀면서 주의할 점이 2가지 정도 존재했습니다.

• 숫자 0은 첫번째 자리만 갈 수 없고 다른 자리로는 갈 수 있습니다.
• 서로 다른 자리의 숫자를 바꾸었을 때의 결과가 기존 숫자와 동일하더라도 다른 숫자로 인식해야합니다.
  • 예를 들어 100, 2의 입력이 주어졌다고 가정해봅시다. 100에서 두번째 자리 숫자와 세번째 자리 숫자를 바꾸었을 때의 결과는 100으로 기존 숫자와 동일합니다. 서로 다른 자리의 숫자를 바꾸었을 때 기존 숫자와 동일하더라도 다른 숫자로 인식해야합니다.
  • 따라서 동일한 숫자를 체크하는 visited 배열을 K개를 만들어 visited[T]는 T번 연산을 수행했을 때 중복된 숫자를 체크하는 용도로 사용하였습니다.

2. 코드

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def bfs(number):
    visited = { i:set() for i in range(1,k+1)}
    length = len(number)
    q = deque([(number,0)])
    while q:
        num, cnt = q.popleft()
        if cnt == k: continue
        for i in range(length):
            for j in range(i+1,length):
                temp = num[:i] + num[j] + num[i+1:j] + num[i] + num[j+1:]
                if i == 0 and num[i] != '0' and num[j] == '0': continue
                if temp not in visited[cnt+1]:
                    visited[cnt+1].add(temp)
                    q.append((temp,cnt+1))
    if visited[k]:
        return max(map(int, visited[k]))
    return -1

n, k = map(int,input().split())
print(bfs(str(n)))