[백준] 2098 외판원 순회

2098 외판원순회

비트마스킹을 활용한 동적계획법.
제한조건으로 순회 노드수 N이 2 <= N <= 16 이므로 dp table을 아래와 같이 정의할 때 O((2^N)(N^2))로 풀 수 있다.

순회의 특성상 어느 노드에서 시작해도 최소 비용을 결정하는 순회경로는 변하지 않을 것이다. 따라서 집합 S, 노드 i에 대해

라고 하면,

가 성립하고

이 구하고자 하는 값이 된다.

부분집합을 구현하는 과정에서 비트마스킹을 사용하게 된다.
부분집합 S를 S의 각 원소가 1인 길이 N인 이진수로 표현한다면
i가 S의 원소라는 것은 S의 번째 비트가 1이라는 것이고, 이것은 S & (1<<i) == 1 또는 (S>>i) & 1 == 1로 확인 할 수 있다.
S의 원소 i를 S에서 제외하는 것은

이므로 S & ~(1<<i)이다.

python code

import sys

N = int(sys.stdin.readline())
W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if W[i][j] == 0:
            W[i][j] = 1e9

dp = [[1e9]*N for _ in range(1<<N)]
dp[0][0] = 0
for S in range(1<<N):
    for i in range(N):
        for j in range(N):
            if S & (1<<j):
                dp[S][i] = min(dp[S][i], dp[S&(~(1<<j))][j] + W[j][i])

print(dp[-1][0])