외판원 순회 2
오늘할 백준 문제는 외판원 순회2이다.
완전탐색을 하면서 모든 경우의 수를 구하고 제일 낮은 코스트를 출력하면 되는 문제이다.
import sys
from itertools import permutations
input = sys.stdin.readline
n = int(input())
w = [list(map(int, input().split())) for _ in range(n)]
for i in range(len(w)):
for j in range(len(w)):
if w[i][j] == 0:
w[i][j] = float("inf")
n_list = list(range(1, n))
cost_list = []
for permu in permutations(n_list, len(n_list)):
permu = (0,) + permu +(0,)
cost = 0
# print(permu)
# print(permu[0],permu[1],permu[2], permu[3])
for k in range(len(permu)-1):
cost += w[permu[k]][permu[k+1]]
# print(cost)
cost_list.append(cost)
print(min(cost_list))- 모든 n개의 도시에 모두 방문하는 루트중 코스트가 제일 낮은 경우의 수를 구해야한다.
- 0,0/1,1/2,2/3,3의 값과 0이 올 수 있는 값은 코스트 비용이 0이라 해당 루트는 제외해야한다.
- 그래서 해당 대각선에 있는 0값을 inf(무한) 값으로 치환하여 해당 경우의 수일 때 돌때 코스트의 합이 inf가 되기 때문에 제일 작을 수가 없다.
- 그리고 도시 n개를 순회를 해야하기 때문에 생각하기 쉽게 0을 제외한 모든 순열을 구한 후 앞과 뒤에 0을 붙여 불필요한 계산을 지운다.(출발한 도시로 되돌아오기 때문)
- 왜냐하면 (0->2->3->1)은 (1->0->2->3), (3->1->0->2), (2->3->1->0->2)의 비용과 동일하기 때문에 불필요한 계산을 줄일 수 있다.
- 순열마다 발생하는 비용을 리스트에 넣어 제일 최솟값이 해당 루트에 제일 적은 비용이 된다.
