[2098번] 외판원 순회(TSP, 비트 마스킹)

2098번: 외판원 순회

 

외판원 순회 (모든 도시를 순회하는 최단 거리)

• n≤11일 경우: 브루트포스(O(n!))
• n≤12일 경우: 백트래킹
• n≤16일 경우: DP + BitMasking (n2∗2n)

 

분석

D[c][v] : 현재 도시 c, 현재까지 방문한 모든 리스트 v, 앞으로 남은 모든 도시를 경유하는데 필요한 최소비용

점화식 : D[c][v] = min(d[c][v], d[i][v|(1<<i)] + W[c][i])

풀이

import sys
imput=sys.stdin.readline

# 도시개수
n=int(input())
# 비용 행렬
w=[]

for i in range(n):
    w.append([])
    w[i]=list(map(int,input().split()))

d=[[0 for j in range(1<<16)] for i in range(16)] # n(1~16)

def tsp(c,v):
    if v==(1<<n)-1: # 모든노드 방문
        if w[c][0] ==0: # 시작도시로 들어갈 수 없음
            return float('inf')
        else:
            return w[c][0]

    if d[c][v]!=0: # 이미방문
        return d[c][v]

    res = float('inf')
    for i in range(0,n):
        if (v&(1<<i))==0 and w[c][i]!=0:  # 방문한 적없고, 갈수 있는 도시
            res = min(res, tsp(i, (1<<i))+w[c][i])
    d[c][v] = res
    return d[c][v]

print(tsp(0,1))