외판원 순회

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

문제

외판원 순회 (Traveling Salesman problem, TSP)

외판원 순회 문제는 여러 도시와 그 도시들 사이의 거리가 주어졌을 때, 모든 도시를 정확히 한 번씩 방문하면서 가장 짧은 거리를 걸으며 돌아오는 문제입니다.

입력

• 첫째 줄에 도시의 수 N이 주어진다. 2 ≤ N ≤ 16
• 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.
• 항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

• 첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제

입력

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

출력

35

---

풀이

외판원 순회 문제는 NP-hard 문제로 알려져 있어, 모든 가능한 경우의 수를 확인해야 합니다. N! 가지의 경우의 수가 있으므로 이를 완전탐색으로 해결하기 위해서는 시간복잡도가 매우 큽니다. 하지만 비트마스크와 동적계획법(DP)를 사용하여 이 문제를 해결할 수 있습니다.

파이썬 코드

n = int(input())
w = [list(map(int, input().split())) for _ in range(n)]
dp = [[None] * (1 << n) for _ in range(n)]
INF = float('inf')

def find_path(last, visited):
    # 모든 도시를 방문했을 때
    if visited == (1 << n) - 1:
        return w[last][0] or INF

    # 이미 계산된 경우
    if dp[last][visited] is not None:
        return dp[last][visited]

    tmp = INF
    for city in range(n):
        if visited & (1 << city) == 0 and w[last][city] != 0:
            tmp = min(tmp, find_path(city, visited | (1 << city)) + w[last][city])

    dp[last][visited] = tmp
    return tmp

print(find_path(0, 1 << 0))

코드 설명

1. 입력을 받아서 도시 수 n과 비용 행렬 w를 설정합니다.
2. dp 배열을 생성하여 중복 계산을 방지합니다.
3. 재귀 함수 find_path는 현재 도시와 이미 방문한 도시의 상태를 인자로 받습니다.
4. 모든 도시를 방문했을 경우 시작 도시로 돌아가는 비용을 반환하거나, 갈 수 없으면 무한대 값을 반환합니다.
5. 이미 계산된 경우 저장된 값을 반환합니다.
6. 모든 도시에 대하여 아직 방문하지 않았고, 가는 길이 있는 경우를 확인하며 최소 비용을 계산합니다.
7. 계산된 값을 dp에 저장하고 반환합니다.

마지막으로 find_path(0, 1 << 0)을 호출하여 문제를 해결합니다.