[백준] 2098 외판원 순회

---

외판원 순환 문제( TSP: Traveling Salesperson Problem)이다. TSP는 하나의 시작점에서 모든 도시를 단 한번씩만 방문하여 원래 도시로 돌아오는 문제를 말한다.

 

TSP를 해결하기 위한 방법은 두 가지가 존재한다.

1. 완전탐색 O(N!)

2. 다이나믹 프로그래밍 O(N^2 * 2^N)

 

만약 도시의 개수가 10개 이하라면 완전탐색도 사용이 가능하다. 하지만 일반적으로 다이나믹 프로그래밍을 사용한다. 그리고 방문한 도시를 구분하는 방법이 이전에 풀었던 문제와 다른데 비트 마스크를 사용한다.

 

만약 1, 2, 3, 4의 도시가 존재한다면, 1과 2 도시를 방문할 경우 1100과 같이 나타낸다. 비트 마스크로 나타내어 만약 방문한 도시가 동일하다면 비용도 동일하기 때문에 굳이 모두 직정 방문하는 것이 아니라 DP를 사용하여 값을 바로 반환한다.

 

import sys
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
readline = stdin.readline

N = int(readline())
graph = [list(map(int,input().split())) for i in range(N)]
dp=[[0]*(1<<N) for _ in range(N)]
MAX = sys.maxsize


def TSP(cur, visited):
    # 모든 도시를 방문한 경우 
    # 현재 도시와 시작 도시간 경로가 있다면 해당 값을 반환
    if visited == ((1 << N) - 1):
        return graph[cur][0] or MAX

    # 이미 방문한 도시인 경우
    if dp[cur][visited]:
        return dp[cur][visited]
    
    cost = MAX
    for i in range(N):
        # cur과 i 도시간 경로가 존재하고
        # i 가 아직 방문하지 않은 도시라면
        if graph[cur][i] and not visited&(1<<i):
            cost = min(cost, TSP(i, visited|(1<<i))+ graph[cur][i])
    dp[cur][visited] = cost

    return cost

ans = TSP(0, 1)
if ans == MAX:
    print(-1)
else:
    print(ans)