[백준] 2098번 외판원 순회 (Python)

백준 2098 외판원 순회

DP, DFS, 비트마스킹을 사용해야 했기 때문에 굉장히 어려웠다. 비트마스킹은 아직 익숙하지 않기에 조금 까다로웠다. 이 문제는 출발 지점을 내가 직접 정해야 하지만 중요하진 않다. 1 -> 2 -> 3 -> 1 과 2 -> 3 -> 1 -> 2의 값은 같기 때문이다. 다익스트라 알고리즘처럼 DP를 활용해서 문제를 풀면 시간 초과가 나온다. 이 문제에서는 DP를 한 점에서 path에 들어 있는 점들을 지나 시작점으로 향하는 최소비용으로 생각하면 된다. 점화식은

dp[cur][visited] = min(dp[cur][visited], dp[next][visited | (1 << next)] + cost[cur][next])
으로 현재 cost와 다음 마을에서의 최솟값을 더하는 방식이다.

import sys

def DFS(p, path):
    if dp[p][path] != 1e9:
        return dp[p][path]
    
    if path == (1 << (n - 1)) - 1:
        if cost[p][0]:
            return cost[p][0]
        else:
            return 1e9
        
    for i in range(1, n):
        if not cost[p][i]:
            continue
        if path & (1 << i - 1):
            continue
        dp[p][path] = min(dp[p][path], cost[p][i] + DFS(i, path | (1 << (i - 1))))
    return dp[p][path]


input = sys.stdin.readline
n = int(input().strip())
cost = [list(map(int, input().split())) for _ in range(n)]
dp = [[1e9 for _ in range(1 << n)] for _ in range(n)]
# dp[p][path] -> i에서 path에 들어 있는 점들을 지나 0으로 향하는 최소비용

print(DFS(0, 0))