[BOJ 2098] 외판원 순회

문제

---

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

풀이

---

유명한 외판원 순회 문제이다.

비트필드에서의 DP 중에 가장 기본적인 문제이지 않을까 싶다.

방문한 도시들과, 현재 위치가 정해지면 그 이후의 최소 비용은 유일하게 결정된다.

이런 상황을 독립적인 부분 문제가 성립한다고 부르겠다.

N이 16 이하이므로, 방문한 도시들을 비트마스크로 관리해 주면 N * 2 ** N 크기의 DP 테이블에 메모이제이션할 수 있다.

코드

---

import sys

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0] * n for _ in range(2 ** n)]


def tsp(mask, cur):
    if dp[mask][cur]:
        return dp[mask][cur]

    if mask == 2 ** n - 1:
        if graph[cur][0]:
            return graph[cur][0]
        return float('inf')

    res = float('inf')
    for nxt in range(n):
        if (not mask & (1 << nxt)) and graph[cur][nxt]:
            res = min(res, tsp(mask | (1 << nxt), nxt) + graph[cur][nxt])
    
    dp[mask][cur] = res
    return res


print(tsp(1, 0))

문제 조건에서 항상 순회할 수 있는 경우만 입력으로 주어진다 했고, 순회 경로 중에 1번 도시가 포함될 테니 출발점을 0 (1번 도시)으로 둬도 무방하다.