[snippet] TSP.py

백준 2098번. 외판원 순회에 대한 풀이를 외판원 순회(TSP; Traveling Salesman Problem)의 스니펫 느낌으로 작성.

• 편의상 1번 도시가 아닌, 0번 도시부터 시작하도록 한다.
• dp[i][visited] : not visited(i는 이미 visited이므로 제외)인 곳을 모두 거쳐 다시 시작점으로 돌아가는데 드는 최소 비용

import sys
input = lambda: sys.stdin.readline().rstrip()
miis = lambda: map(int, input().split())
INF = int(1e9)
IMPOSSIBLE = -1 # https://www.acmicpc.net/board/view/92092

###############################################

def dfs(i, visited):
    if dp[i][visited] != INF:
        return dp[i][visited] # IMPOSSIBLE 포함
    if visited == (1<<N) - 1: # 모든 도시 방문 완료
        return W[i][0] if W[i][0] else IMPOSSIBLE

    min_dist = INF
    for j in range(N):
        if not W[i][j]:
            continue
        if visited & (1<<j): # i번 도시를 이미 방문했다면
            continue
        dist = dfs(j, visited | (1<<j))
        if dist == IMPOSSIBLE:
            continue
        min_dist = min(min_dist, W[i][j] + dist)
    dp[i][visited] = min_dist if min_dist != INF else IMPOSSIBLE
    return dp[i][visited]

###############################################

N = int(input())
W = []
for _ in range(N):
    W.append(list(miis()))

dp = [[INF] * (1<<N) for _ in range(N)]
ans = dfs(0, visited=0b0001)
print(ans)