[Python]동적계획법3 백준 2098

문제

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

점점 복잡해진다.  tsp문제로 아직도 활발히 연구중인 알고리즘이라고 한다.

우리는 사이클을 찾기위해선 모든 길을 확인해보아야한다.

이때 이전에 방문했던 노드를 방문하지 않아야 한다. 그러기위해선 이전방문노드를 효과

적으로 저장할 필요가 있다.

우리는 비트마스크와 DP를 통해 문제를 해결할수있다.

https://shoark7.github.io/programming/algorithm/introduction-to-tsp-and-solve-with-exhasutive-search

https://shoark7.github.io/programming/algorithm/solve-tsp-with-dynamic-programming

굉장히 잘 설명 되어있는거같다.

기본적으로 모든 노드를 확인하기 위해선O(N!)이 필요하다.

이를 DP를 통해 줄여야한다. 문제를 풀어보자.

비트마스크는 각자리수가 방문한곳를 표시하게 된다. 

DP 배열의 경우 DP[현재노드][방문여부]=비용 으로 나타내게 되며 DP[1][6]=4 라는것은

 현재 [1]에 도착해 있고 [6] 즉 0110 1,2를 방문한 상태라는것이다.재귀를 통해 구현하는

데 보통 재귀는 짧고 간결한대신 처음보는 사람 입장에서는 쉽게 파악하기 힘들수 있다.

문제 예제의 재귀 호출순서이다.

0에서 출발하므로 0에 방문표시 1을 놓고시작한다.

find_path(1,1) 0->1 

0->1로 간경우이다 2,3을 방문할수있다.

find_path(2,11) 1->2

0,1을 방문하고 먼저 2를 방문

find_path(3,111) 2->3

0,1,2를 방문후 3을 방문

find_path(3,11) 1->3

0,1을 방문하고 3방문

find_path(2,1011) 3->2

0,1,3을 방문하고  2방문

0->2를방문했을때

find_path(2,1) 0->2

find_path(1,101) 2->1

find_path(3,111) 1->3

find_path(3,101) 2->3

find_path(1,1101) 3->1

0->3를방문했을때

find_path(3,1) 0->3

find_path(1,1001) 3->1

find_path(2,1011) 1->2

find_path(2,1001) 3->2

find_path(1,1101) 2->1

이제 모두 방문한 상태가 됬다면 마지막 방문노드에서 출발점 0으로 돌아가는 경로를 

더해주고 그중 최솟값을 찾으면된다.

import sys
 
N=int(sys.stdin.readline())
W=[]
INF=sys.maxsize
for _ in range(N):
    W.append(list(map(int,sys.stdin.readline().split())))
DP=[[None]*(1<<N) for _ in range(N)]
 
def find_path(last,visited):#현재위치
    if visited == (1<<N)-1:  # 모두 방문햇다면
        return W[last][0] or INF  # 0으로 가는방법 반환 없으면 INF반환
 
    if DP[last][visited] is not None:  # 이미 계산되어잇다면
        return DP[last][visited]  # 있는값 반환
 
    tmp=INF
    for city in range(N):#모든 도시에서
        if visited & (1 << city) == 0 and W[last][city] != 0:#아직 방문하지 않았고 cur->i로 가는길이 있다면
            tmp=min(tmp,
                    find_path(city,visited | (1<<city)) + W[last][city])
    DP[last][visited]=tmp
    return tmp
 
 
print(find_path(0,1<<0))