백준(BOJ) 1039 교환(Python)

문제 내용

 

BFS 문제.

현재 숫자와 바꾼 횟수에 따라 방문 처리를 해줘야 한다.

그 외에는 크게 어려울 게 없었다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,k=input().split()
visited=[[0]*11 for i in range(1000001)]
visited[int(n)][0]=1
n=list(n)
l=len(n)
k=int(k)
queue=deque()
queue.append([n,0])
def swap(i,j):
    temp=a[i]
    a[i]=a[j]
    a[j]=temp
ans=-1

while queue:
    a,b=queue.popleft()
    if b<k:
        for i in range(l):
            for j in range(i+1,l):
                swap(i,j)
                x=int(''.join(a))
                if len(str(x))==l and not visited[x][b+1]:
                    visited[x][b+1]=1
                    queue.append([a.copy(),b+1])
                swap(j,i)
    else:
        ans=max(int(''.join(a)),ans)
print(ans)

 

시간이 되게 오래 걸렸다.

아마 시간복잡도를 줄이는 다른 방법이 있을 것 같다.