백준 2098 : 외판원 순회

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

2098번: 외판원 순회

 

 

해결 방법 : 완전 탐색 + DP 메모제이션(Bitmask)

- 처음 접하는 문제 유형이라 공부하면서 풀었다. (참고한 사이트는 링크로)

• 비트 마스크 : TSP 문제는 결국 완전 탐색을 해야하는데, 이 때 메모제이션을 접목하기 위한 방법이다. 
  
  • (비트 마스크 연산에 대한 이해는 링크를 참조)
• 코드를 보면, 메모제이션을 적용한 것 외에는 dfs 응용 문제와 크게 다르지 않다.  

 

import sys
input = sys.stdin.readline

def solution(n, arr):
    M = [[0] * (1 << n) for i in range(n)] # 메모제이션 
    done = (1 << n) - 1 # 모든 경로를 탐색한 경우의 이진 표현

    def tsp(node, path):
        if path == done: # 마지막 노드에서 첫번째 노드로 갈 수 없다면 비용은 무한대이다.
            return arr[node][0] if arr[node][0] != 0 else float('inf')
        if M[node][path] != 0: # 남은 구간이 이전 탐색과 중복되어 메모제이션으로 단축
            return M[node][path]

        cost = float('inf') # 현재 경로 상태에서 순회를 마칠때까지의 비용
        for nextNode in range(1, n): 
            if arr[node][nextNode] == 0 or path & (1 << nextNode) > 0: # 노드가 이어지지 않거나, 이미 탐색한 노드라면 skip
                continue 
              # 탐색 가능한 nextNode로 갔을 때의 최소값
            cost = min(cost, arr[node][nextNode] + tsp(nextNode, path | (1 << nextNode)))
        M[node][path] = cost # 현재 path, 현재 방문 node 경우에서의 최종 최소 비용을 저장

        return cost

    return tsp(0, 1)

if __name__ == '__main__':
    n = int(input())
    arr = [list(map(int, input().strip().split())) for i in range(n)]
    result = solution(n, arr)
    print(result)