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

n = int(input()) W=[] mincost = 0 for i in range(n) :     row = list(map(int, input().split()))     W.append(row)     mincost = mincost + sum(row) def DFS(start, now, cost, gone) :     global mincost     if len(gone) == n :         if W[now][start] != 0 :             mincost = min(mincost, cost + W[now][start])         return     for j in range(n) :         if cost + W[now][j] <= mincost :             if W[now][j] != 0 and j != start and j not in gone :                 DFS(start, j, cost + W[now][j], gone + [j]) for i in range(n) :     DFS(i, i, 0, [i]) print(mincost)

1. 인풋을 받아서 코스트 테이블 W를 작성한다. 이때 모든 항의 합을 구해두면 mincost의 upperbound가 된다.

max는 0으로 시작하면 되지만 min에 무한대를 쓸순 없으니 이렇게 어퍼바운드를 땄는데, 나중에 보니 sys.maximize라는 좋은 기능이 있었다. 지식이 늘었다.

2. 시작위치 start, 현재위치 now, 누적코스트 cost, 갔던곳 gone을 입력받았을때, 다음에 갈 모든 위치 for j에서 자기 자신을 실행하는 재귀함수 DFS()를 정의.

3. 재귀의 반복은 gone에 모든 위치가 다 담기거나, 다 안돌았더라도 cost가 mincost을 오버했다면 끝난다. gone에 모든 위치가 담기는 방식으로 재귀가 끝나면 마지막으로 start로 돌아오는 비용을 더하고, cost가 mincost보다 작은지 비교해서 작다면 mincost를 갱신한다.

4. 모든 도시 for i에 외판원 하나씩 심고 DFS를 실행해서 mincost를 출력

 

생각해보면 DFS는 DFS라는 새로운 개념을 이해해서 그것대로 뭔가를 구현하는게 아니라, 그냥 인간의 사고방식대로 하나씩 확인해서 모든 경우를 따지는 재귀를 구현하면 그게 결과적으로 DFS가 되는 것 같다.

N-Queen에 비해 DFS에 입력할 변수는 많지만, DFS 안에서 따져야할 것은 적다. 입력값으로 다 정해두고, DFS의 재귀에서 따질 다음 단계의 입력값이 어떻게 변할지만 따지면 되니 오히려 더 나았던 것 같기도 하다.