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

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

10971번: 외판원 순회 2

• 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이번 10971문제는 그중에서도 간단한 문제였다.
• 처음에는 DFS나 BFS로 생각해서 풀다가 플로이드 워셜로도 풀까 생각했었는데, 방문처리를 하는 과정을 어떻게 할까 하다가 완전 탐색으로 풀이를 하였다.
• 이문제는 N이 10까지여서 괜찮지만, 다른 TSP 문제를 풀 때는 무조건 시간 초과가 발생할 거 같아서, 다른 풀이도 한번 생각해봐야겠다.
• 숫자 n이 주어지면 0부터 n-1까지의 정수가 담긴 리스트를 하나 만들어준다.
• 그 리스트를 permutation함수를 이용해서 나오는 경우의 수를 모두 계산해준뒤, for문으로 하나하나 경로를 다 돌면서 어떤 경로의 값이 가장 작은지를 비교해주었다.
• 함수 안에서 for문의 값이 0이 아니면 data에 있는 값을 ans에 더해주었고, 마지막에는 도착점에서 출발점까지의 거리 또한 0이 아닐 경우에 더해서 총 경로 이동 값을 return 해주었다.

import sys
from itertools import permutations
input = sys.stdin.readline

n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]

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

def function(List):
    ans = 0
    for i in range(n-1):
        if data[List[i]][List[i+1]] != 0:
            ans += data[List[i]][List[i+1]]
        else:
            return False
        
    if data[List[-1]][List[0]] == 0:
        return False
    else:
        ans += data[List[-1]][List[0]]
    
    return ans

ans = 987654321
for List in permutations(n_num):
    result = function(List)
    if result != False:
        if ans > result:
            ans = result
print(ans)