백준 2098 외판원 순회

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

알고리즘에서 유명한 문제인 TSP 문제이다.

TSP 문제의 가장 쉬운 해결방법은 완전탐색이고, 완전탐색은 대부분 dp로 해결이 가능하다(특별한 케이스를 제외하고)

TSP문제는 어떤 지점에서 다른 지점들을 거쳐 시작지점으로 돌아오는데, 이는 반드시 cycle을 형성하게 되어있다. 즉, 어느 지점에서 시작하나 최솟값은 항상 같다는 것이다.

시작지점을 0번노드로 설정하고, visited를 인자로 주어 비트마스킹을 통해 어떤 노드를 방문하였는지 확인할 수 있다.

동적 테이블은 각 노드마다의 방문상태를 저장하였는데,
예를 들어, 1번노드에 위치해있고 방문한 노드가 0,1,2라면 dp[1][7]로 나타낼 수 있고,
이는 현재 state에서 cycle을 만드는데 드는 최소비용이다.

시작 지점부터 방문 안한 노드를 탐색해 재귀를 통해 동적할당을 하게되는데,
문제 예시에서 처럼 노드가 4개라고 가정했을때
가장 시작지점 dp[0][1]에서 사이클을 만드는데 최소비용을 탐색하기 위해 비교해야 할 대상은,
dp[1][3], dp[2][5], dp[3][9]를 비교해야 한다.

dp[1][3]을 구하기 위해선 방문 안한 2번과 3번으로 갔을때 비용을 최소로 만드는 사이클을 구해야 하고, 이는 곧 재귀를 통해 dp를 채워나가면 된다.

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

circuit = (1<<n) - 1
dp = [[math.inf]*(1<<n) for i in range(n)] ## k번째 도시에서 k번째 도시로 오는데 최솟값
## 시작 도시는0번
def dfs(node,visited):
    if visited == circuit:
        if w[node][0]:
            return w[node][0]
        else:
            return math.inf
    if dp[node][visited] != math.inf: ## dp되어있다면 반환
        return dp[node][visited]

    for i in range(1,n):
        if w[node][i] and not visited & (1<<i):
            dp[node][visited] = min(dp[node][visited], dfs(i,visited|(1<<i)) + w[node][i])
    return dp[node][visited]

print(dfs(0,1<<0))