[외판원 순회/G1/Python3]

2098번 외판원 순회 G1

 

문제
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다. 각 도시 간에 이동하는데 드는 비용은 행렬 W [i][j] 형태로 주어진다. W [i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W [i][j]는 W [j][i]와 다를 수 있다. 모든 도시 간의 비용은 양의 정수이다. W [i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W [i][j]=0이라고 하자. N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

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

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

 

다이나믹 프로그래밍, 비트마스킹, 비트필드를 이용한 다이나믹 프로그래밍, 외판원 순회 문제

 

현재까지 방문한 정점들을 비트마스킹으로 기록하여 문제를 풀이했다.

어느 정점에서 시작해도 동일한 경로를 탐색하게 된다.

 

가능한 모든 비트마스킹의 경우는 2^16 = 65536이므로, 거리 정보를 dp에 담았다.

중복 탐색을 제외한 모든 경로를 탐색하여, 최솟값을 출력하였다.

 

 

import sys
n = int(sys.stdin.readline())

w = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# visit의 경우는 2진수 형태로 관리
# 현재 위치는 해당 배열의 1번째 값으로 관리

dp = [[0] * 65536 for _ in range(16)]

# cur, visit
# 시작점은 0에서 시작, 어디에서 시작해도 상관은 없다
pos = [[0, 0b0000000000000000]]

# n-1번만 이동하면 된다 (어차피 마지막은 시작한 위치로 이동해야 함)
for _ in range(n-1):
    next_pos = []
    for cur_v, visit in pos:
        cur_min_v = dp[cur_v][visit]
        for i in range(1, n):
            # 이미 지나온 점이거나, 방문 불가(가치가 0)인 경우 제외
            if visit & (1<<i) > 0 or w[cur_v][i] == 0:
                continue
            next_visit = visit | (1<<i)
            # 최초로 방문 했을 때만 bfs에 넣어야 함
            if dp[i][next_visit] == 0:
                next_pos.append((i, next_visit))
                dp[i][next_visit] = w[cur_v][i] + cur_min_v
            dp[i][next_visit] = min(w[cur_v][i] + cur_min_v, dp[i][next_visit])
    pos = next_pos
    
# 각 거리는 최대가 100000이므로, 최대 120만을 넘을 수 없음
result = 12000000
for cur_v, visit in pos:
    # 시작한 위치로 갈 수 없는 경우 제외
    if w[cur_v][0] == 0:
        continue
    result = min(result, dp[cur_v][visit] + w[cur_v][0])
print(result)​

 

 

---