백준 10971 외판원 순회 2 파이썬

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

10971번: 외판원 순회 2

순열 함수를 알고 있으면 쉬운 문제였다.

pypy로 제출하면 AC받을 수 있다.

import sys
import itertools
input = sys.stdin.readline

n = int(input())
s = [list(map(int,input().split())) for _ in range(n)]#i->j거리를 나타내주는 map를 만들어줌
t = list(itertools.permutations([i for i in range(n)], n))#순열을 구해줌 모든 경로의 경우의 수를 탐색하기 위해.
re = sys.maxsize
for k in t:
    c = 0
    e = 0
    for i in range(n-1):
        if s[k[i]][k[i+1]]!=0:#i->j가 0이 아니면 갈 수 있으니 비교값 c에 더해줌
            c+=s[k[i]][k[i+1]]
        else:#못 가면 그 이상은 볼 필요가 없으니 멈춰줌
            e = 1
            break
    if s[k[n-1]][k[0]]!=0:#마지막 경로에서 처음 경로로 오는 경우로 체크해줌
            c+=s[k[n-1]][k[0]]
    else:
            e = 1
            
    if e ==0:#모는 경로를 지나 원래대로 돌아왔으면 결과값 re를 갱신해줌
        re = min(re,c)
print(re)