[BOJ 2098] 외판원 순회(Python)

문제

외판원 순회

---

문제 해설

외판원 순회의 기본적인 문제입니다. 처음에 외판원 순회라는 알고리즘을 이해하지 못해 오래 걸렸던 문제였습니다.

외판원 순회 알고리즘을 사용할 수 있는 환경은 모든 노드가 순회가 되어야 한다는 것인데, 일단 순회만 가능하면 어떤 노드에서 시작하든 상관이 없습니다.
ex) 1->3->2->4->1 == 3->2->4->1->3
위와 같이 어차피 지나쳐야 하는 간선은 똑같기 때문입니다.

아직까지도 다항 시간안에 해결할 수 있는 해결법을 제시 한 사람은 없으며 그나마 정석적인 풀이라고 자리잡아가는 방법이 비트마스크, DFS, DP를 이용하는 것입니다.

비트마스크를 쓰는 이유는 노드들의 방문 상태를 체크 하기 위해서 입니다. 즉, 현재 어떤 노드에 있으며 어떤 노드들을 지나쳐 왔는지에 대한 정보를 저장할 그릇이 필요합니다. 단순하게 리스트의 차원을 늘리며 저장하기엔 메모리가 너무 부족합니다. 가장 효율적으로 저장할 수 있는 방법이 int 형태의 비트마스크로 저장하는 것입니다. (단, N이 20이 넘어가면 2^20만큼의 리스트 용량이 필요하기 때문에 주의하세요!)

dfs는 어떤 정점에서 시작해도 상관없고, 단순히 DP를 채우는 방법 중에 하나입니다.

dp는 중복되는 계산을 줄이기 위해서 사용합니다. dfs를 진행하다보면 중복되는 값이 자주 발생하는데 이것을 줄이기 위해 DP를 사용합니다.
DP[현재노드][방문한 노드들] = 앞으로 나올 노드들의 종점 까지 도달하는 최소 비용입니다.

풀이 순서는 다음과 같습니다.

1. 정점을 아무거나 정합니다.

2. dfs를 시작합니다. DP를 Top-Bottom형식으로 채우기 위해서입니다.

3. 방문하지 않은 노드들을 탐색합니다. 여기서 방문 하지 않은 노드들을 모조리 방문하여 최소값을 얻어냅니다.

4. 모두 방문 했으면 현 노드에서 종점까지 가는 비용을 리턴합니다.

5. DP값이 있으면 그 값을 리턴합니다.

제일 헷갈리는 부분이 DP의 값이 어떤 값이 들어가는가 였는데, 예를 들어 노드 번호가 0~4, 첫노드 : 0 라면
DP[1][00011] = 5 의 뜻은
012340, 013420, 014320, ... 의 01로 시작하는 모든 경우의 수의 최소값이 5라는 뜻입니다. 이러한 값들이 계속 리턴되어 첫 시작점에는 모든 경우의 수의 최소값이 최종적으로 리턴됩니다..

참고

---

풀이 코드

import sys

input = sys.stdin.readline
n = int(input())
inf = sys.maxsize
graph = [list(map(int, input().split())) for _ in range(n)]
# dp[1][1011(2진수)] = 5
# 0,1,3의 노드를 지난 후 현재 1번노드이며 추후 모든 동선을 DFS탐색할 것
# 0번 노드로 가는 최소 값이 5이다.
# top-bottom 형식의 재귀 함수로 인해 dp의 값은 최소값을 메모라이징하고
# dp는 한번 저장되면 갱신할 필요가 없다.
dp = [[inf] * (1 << n) for _ in range(n)]

# tsp 시작
# cur = 현재 노드, visited = 지난 노드들의 비트필드
def tsp(cur, visited):
    global n
    # 모두 방문한 경우
    if visited == (1 << n) - 1:
        # graph[cur][0] == 0 이면 inf 반환
        return graph[cur][0] or inf

    # 이미 dp에 값이 있어 계산할 필요 없을 경우
    if dp[cur][visited] != inf:
        return dp[cur][visited]

    min_v = inf
    for next in range(n):
        # 방문 하지 않았고, 이어져 있는 노드들 탐색
        if not visited & (1 << next) and graph[cur][next] != 0:
            # 다음 노드를 방문체크를 해준채 tsp에 넣고
            # dfs를 진행해서 최소값을 갱신.
            min_v = min(min_v, tsp(next, visited | 1 << next) + graph[cur][next])
    # 최종적으로 dp에 값을 넣어준다.
    dp[cur][visited] = min_v
    # 상위 깊이 dfs에 값을 넘겨준다.
    return min_v


print(tsp(0, 1))

---