[python] 백준 10971 외판원 순회2

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

10971번: 외판원 순회 2

문제해결

dfs 는 써야된다는 생각이 바로 든다. (계속 반복적으로 판별하여 이동하므로)

마지막에 처음 시작지점으로 돌아와야 하므로 처음 시작점은 기억해두어야한다.

현재 지점(now)에서 이동할 지점(next)로 갈 때 주의할 점은 한번도 가본적이 없어야 한다는 것(단 시작점으로 마지막 이동할 때 제외)과 지금 비용이 최소비용일 가능성이 있어야 한다는 점이다.

 

CODE

import sys
input = sys.stdin.readline
INF = sys.maxsize
def TSP(start,now, total, visited):
    global ans
    if len(visited) == n:
        if cost[now][start] !=0:
            ans = min(ans, total+cost[now][start])
        return
    for next in range(n):
        if cost[now][next] != 0 and next not in visited and total<ans:
            visited.append(next)
            TSP(start, next, total+cost[now][next], visited)
            visited.pop()


if __name__ == "__main__":        
    n = int(input())
    cost = [list(map(int, input().split())) for _ in range(n)]
    ans = INF
    for s in range(n):
        TSP(s,s,0,[s]) 
    print(ans)