[TSP] 백준 10971 문제 풀이

나는 브루트포스 방식을 이용해서 문제를 풀었다. 그거밖에 생각이 나지 않았다. 모든 경우를 탐색해봐야 하는데 그 방법을 찾는 것도 알고리즘 초보인 나에게는 너무 어려웠다.

 

모든 순열을 탐색해야하는데 이 방법은 찾아보았다. w[i][j]가 도시 i에서 j로 가는 비용이라고 하였기 때문에 w[i][i+1]과 같은 방식으로 거리비용을 세야지 모든 도시를 경유할 수 있다. 

permutation을 이용하여 0부터 n-1까지의 수를 순열로 짜고 그 경우의 수마다의 비용을 구한다.

예를 들어 도시를 0,1,2,3이 있다고 할 때 perm = [3 1 2 0]이라면  3->1 1->2 1->0으로 가는 비용이다. 그렇게 모든 경우를 다 탐색해본 후 최소 비용을 구하면 된다. 

 

import itertools

n = int(input())
distance_cost = []

min_distance = float('inf');
for i in range(n):
    input_list = list(map(int, input().split()))
    distance_cost.append(input_list)
print(distance_cost)

points = [i for i in range(n)]


def sum_distance(perm):
    distance = 0

    for j in range(0, n - 1):  # for문을 도는 동안 세 도시를 돈다.
        if distance_cost[perm[j]][perm[j + 1]] != 0:  # 갈 수 있는 도시만
            distance += distance_cost[perm[j]][perm[j + 1]]
        else:
            return -1
    if distance_cost[perm[-1]][perm[0]] != 0:  # 시작점으로 돌아오는 비용
        distance += distance_cost[perm[-1]][perm[0]]
    else:
        return -1

    return distance


for i in itertools.permutations(points):  # 순열마다 돈다
    perm = list(i)
    result = sum_distance(perm)
    if result != -1:
        min_distance = min(min_distance, result)
print(min_distance)