백준을 풀면서 코드는 간단하지만 이해하기 정말 어려웠던 문제이다.
대표적인 NP(Non-deterministic Polynomial time) 문제로, 시간복잡도가 다항시간내에 문제를 해결할 수 있는 문제이다.
ex) 2n , n! , nn 등..
즉, 아무리 알고리즘을 사용하여 시간을 최대한 줄여도 N이 커지면 시간이 기하급수적으로 늘어나는 것이다.
출처 : https://www.acmicpc.net/problem/10971
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
외판원 순환 문제는 어디서 시작해도 결국 순환하는 길은 똑같기 때문에 시작 지점을 A(첫번째)으로 정해서 시작한다.
시간 복잡도를 줄이기 위해 BitMask를 사용하였다.
ex) A,B,C,D,E 가 있고 A에서 시작 할 때 BitmMask : 00001
TSP함수는 now에서 start로 돌아갈 때 드는 비용을 반환한다.
import sys
input = sys.stdin.readline
def TSP(now, visited):
if dp[now][visited]:
return dp[now][visited]
if visited == (1<<N) -1:
return W[now][0] if W[now][0] > 0 else sys.maxsize
cost = sys.maxsize
for i in range(1,N):
if not (visited >> i)%2 and W[now][i]: # 방문한 적이 없고, 길이 있을 때
tmp = TSP(i, visited|(1<<i))
cost = min(cost, tmp + W[now][i])
dp[now][visited] = cost
return cost
N = int(input())
W = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(1<<N) for _ in range(N)]
print(TSP(0,1))