문제

• 문제 링크

외판원 순회 = Traveling Salesman Problem = TSP

이 글에서 테스트케이스가 추가되면서, 그동안 떠돌아다니던 외판원 순회 풀이의 허점이 발견되었다.

INF는 아직 한번도 해당 상태가 오지 않음을 의미하는데,
기존 코드에서는 다음 정점을 다 돌았음에도 아무 정점도 가지 못하는 상태는 INF와 다름에도 INF로 유지하였기 때문에 매번 새로 방문한 척 계산해야 한다.

필자의 코드에는 IMPOSSIBLE이라는 변수를 새로 만들어, INF와 다른 상태임을 구별해주었다.

풀이

• 편의상 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

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

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)