[백준] 1039 교환 파이썬

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

1039번: 교환

 

 

이 문제가 bfs라고..? 하면서 풀이를 봤다

숫자이긴 하지만 어쨌든 문자열이고, 교환을 통해 완전 탐색을 진행해야 한다는 점에서 bfs를 사용한 것으로 보인다.

 

풀이를 보고 나니, 어렵지 않은 코드였다.

그냥 알고리즘 자체가 생각이 안 났음..ㅠ

 

그런데 풀이를 보다가 시간복잡도에 대한 의문이 들었다. 

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())


def bfs(N, K):
    M = len(str(N))

    q = deque()
    q.append((N, 0))
    visited = [(N, 0)]

    answer = -1

    while q:
        n, k = q.popleft()
        if k == K:
            answer = max(answer, n)
            continue
        n = list(str(n))
        for i in range(M - 1):
            for j in range(i + 1, M):
                if i == 0 and n[j] == "0":
                    continue
                n[i], n[j] = n[j], n[i]
                nn = int("".join(n))
                if (nn, k + 1) not in visited:
                    visited.append((nn, k + 1))
                    q.append((nn, k + 1))
                n[j], n[i] = n[i], n[j]

    return answer


print(bfs(N, K))

 

큐 한 번 pop할 때마다 M**2만큼 돌 텐데, depth가 K이니까 시간복잡도가 엄청 커지는 거 아닌가..?

(원래 수)

|

M**2 // 2 개의 경우의 수

|

M**2 //2 개의 경우의 수의 각각의 M**2 //2 개의 경우의 수...

 

이런식으로 지수함수의 발산 마냥 되는 거 아닌가 생각했다.

 

그런데 좀 더 생각해보면

visited로 중복을 제거해주는데, 이렇게 하면 depth의 증가마다 엄청 쌓일 것 같았던 수들이 그렇게 많이 쌓이지 않는다.

거의 다 중복이 일어나 추가되는 것은 몇 개 없다. (임의의 수를 두고 일일이 해본다)

 

그래서 시간복잡도가 통과되는 것 같다.

 

 

------------------------------------------------------------

어디까지나 개인적인 해석이므로 틀릴 수 있습니다. (참견 환영)