백준 외판원 순회 파이썬 ( 동적 계획법 [DP], 비트마스크 )

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

2098번: 외판원 순회

외판원 순회 문제의 경우 TSP 문제라고, 컴퓨터 과학에서 상당히 오랜 기간, 많은 사람들이 연구해온 분야라고 한다. 문제 내용은 간단하지만 해답을 구하는 과정의 시간복잡도가 상당히 높아서 관련연구가 계속 진행되어 온 것 같다. 연구가 오래된 만큼 아주 다양한 풀이 방법이 있다고 한다.

 

완전탐색과 순열을 이용한 풀이로 각각 한번씩 풀어봤는데, 이번에 다이나믹 프로그래밍을 학습하는 과정에서 다시 접하게 되었다. 

몇 시간 정도 고민 끝에 동적계획법으로 풀이하는 법을 생각해내지 못해서 풀이를 찾아봤는데, 비트마스크라는 개념과 함께 적용됨을 확인했고 문제이해를 위해 비트 연산에 대한 학습을 조금 하게 되었다. 학습에 도움된 깃허브 주소를 함께 첨부한다.

https://shoark7.github.io/programming/knowledge/some-useful-bit-tricks-and-usages

현실에서 유용한 Bitwise 연산 및 활용 모음

 

DP / 비트마스크 이용한 풀이

하기 풀이는 함께 정글에서 공부하는 동기가 작성한 코드이다. 동일한 방식으로 푼 몇 가지 코드를 보았지만 가장 잘 작성 한 것 같다. 추후 다시 학습하고자 첨부했다. 입력 값을 제외하면 불과 12줄정도에 불과한 코드이지만, 이 정도의 코드를 생각해내는 것은 해결 방향에 대해 완벽하게 사고과정을 마친 후에 작성이 가능한 것 같다. 상당히 잘 작성한 코드 같다.

import sys
A=[]
def go(now, trace):  
    if dp[now][trace]:
        return dp[now][trace]
    if trace == (1 << N)-1: # 모든 도시 방문 완료시,
        return path[now][0] if path[now][0] > 0 else MAX  #마지막 도시에서 출발도시로 가는 비용 리턴

    cost = MAX
    for i in range(1, N):
        if not trace & (1 << i) and path[now][i]: #비트 마스크를 이용한 방문확인 
            val = go(i, trace | (1 << i))         #recursion & 방문처리
            cost = min(cost, val+path[now][i])    #여러가지 case 중 최솟값 갱신

    dp[now][trace] = cost
    return dp[now][trace]
N = int(input())
path = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (1 << N) for _ in range(N)]
MAX = sys.maxsize

print(go(0, 1))