[백준10971] 외판원 순회 2

문제

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

10971번: 외판원 순회 2

 

생각의 흐름

---

1. n개의 도시들을 1부터 n까지 넘버링하여 리스트에 삽입한다.
2. 도시 리스트를 next_permutation() 함수를 이용해 가능한 모든 순열마다 input으로 주어진 weight 정보를 이용해 cost를 계산해 비교한다.(브루트포스)
3. 이 때, weight가 0인 경우는 길이 존재하지 않는 것이므로 고려할 필요가 없어 건너뛴다.
4. cycle을 만들어야하므로 매 순열마다 [0]번째 원소를 맨 마지막에 append해준다.

 

깨달은 점

---

최소비용거리를 구하는 문제를 크루스칼, 프림, 다익스트라 등이 아닌 순열을 이용해 브루트포스로 풀 수도 있다는 걸 배웠다.

 

코드

---

def next_permutation(arr):

    n = len(arr)-1
    i = n
    while arr[i-1] > arr[i]:
        i -= 1
        if i == 0:
            return -1

    j = i-1
    diff = 10000
    position_to_switch = 0
    for k in range(i, n+1):
        if arr[k]-arr[j] > 0:
            diff = min(diff, arr[k]-arr[j])
    for m in range(i, n+1):
        if arr[m]==arr[j]+diff:
            position_to_switch = m
            break
    temp = arr[j]
    arr[j] = arr[position_to_switch]
    arr[position_to_switch] = temp
    temp_list = arr[j+1:]
    temp_list.sort()
    arr = arr[:j+1]
    arr = arr + temp_list
    
    return arr


if __name__=='__main__':

    num_of_city = int(input())
    weight = []
    for i in range(num_of_city):
        weight.append(list(map(int, input().split())))
    
    city = []
    for i in range(num_of_city):
        city.append(i)

    # the number of permutation
    num_of_per = 1
    for i in range(num_of_city-1):
        num_of_per *= i+1
 
    possible_path = []

    # making cycle path
    path = city[0:]
    path.append(city[0])
    possible_path = path[0:]
    
    cost = 1000000 * num_of_city
    temp_cost = 0
    for j in range(len(possible_path)-1):
        if j != len(possible_path)-1:
            temp_cost += weight[possible_path[j]][possible_path[j+1]]

        # when w[i][j]==0
        if weight[possible_path[j]][possible_path[j+1]]==0:
            temp_cost = 1000000 * num_of_city
            break
    cost = min(cost, temp_cost)

    middle_point = path[:-1]
    for j in range(num_of_per-1):
        middle_point = next_permutation(middle_point)
        path2 = middle_point[0:]
        path2.append(middle_point[0])
        possible_path = path2[0:]

        temp_cost = 0
        for k in range(len(possible_path)-1):
            temp_cost += weight[possible_path[k]][possible_path[k+1]]

            # when w[i][j]==0
            if weight[possible_path[k]][possible_path[k+1]]==0:
                temp_cost = 1000000 * num_of_city
                break
        cost = min(cost, temp_cost)
    print(cost)