[백준/python]2098번 외판원 순회 - bitmasking

알고리즘분석 시간에 배웠던 NP 중 하나인 TSP 문제다. N이 작은 경우 DP와 비트마스킹을 통해 풀 수 있다.

import sys
limit_number = 150000
sys.setrecursionlimit(limit_number)
N=int(input())

#이동 가능한 도시 경로 작성
path=[[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    line= list( map ( int, input().split() ) )
    for j in range(N):
        path[i][j]= line[j]


dp=[[0 for _ in range(1<<N)] for _ in range(N)] #dp[N][1<<N]

VISITED_COMPLETE = (1<<N) -1 
INF= float('inf')


def visiting(last, visited):
    
    if visited==VISITED_COMPLETE :
        return path[last][0] or INF

    if dp[last][visited]!=0:
        return dp[last][visited]

    tmp=INF
    for i in range(N):
        if visited & (1<<i) ==0 and path[last][i]!=0: #방문하지 않은 마을 & path 가 존재
            tmp= min ( tmp, visiting(i, visited | 1<<i ) + path[last][i] )

    dp[last][visited]=tmp
    return tmp

sol = visiting(0, 1<<0 ) #방문한 곳이 0번 노드뿐이고, 가장 최근에 0번 노드를 방문한 경우에서 재귀함수 시작
print(sol)

재귀함수 top down 방식 사용

재귀함수 시작지점 visiting(0,1) = 방문한 곳이 0번 노드 뿐이고 가장 최근에 0번 노드를 방문한 경우, 남은 노드를 모두 방문하고 0번째 노드로 돌아오는 경우 최소 비용

1. DP 설계

비트마스크를 이용해 x번째 도시를 방문했다면 x번째 이진수를 1로 표시한다. N개 도시의 조합을 표현하기 위해서는 N자리 이진수가 필요하고 2^N개의 DP를 통해 십진수로 표현가능. a번째 도시를 방문한 상태일 때 방문한 도시들(b)을 표현하기 위해 2차원 배열을 통해 DP 사용한다. a번쨰 도시를 방문한 상태이고 방문한 도시들b를 제외하고 남은 도시들을 모두 돌고 다시 0번으로 돌아갔을 때 최솟값을 DP에 저장

2. 재귀함수 설계

1번째 if

만약 모두 방문했다면, 다시 처음 도시(0)으로 방문하는 비용 혹은 존재하지 않는다면 inf 반환

2번째 if

만약 해당 경우가 이미 DP에 저장되어 있다면 해당값 반환

3번째 if

방문하지 않은 마을과 해당 마을로 향하는 길이 존재한다면 임의의 마을로 가는 경로 중 최소 값 반환→ 이를 계산하기 위해서는 다음 단계 계산 필요

visiting(0,1) ←min ( visiting( 1, 11), visiting(2, 101), visiting(3, 1001), visiting(4,10001) ) …← 재귀 마지막에 도착 시 ( visiting ( x, 11111) ) x에서 0으로 가는 비용 반환