백준- 외판원 순회(feat.Python)

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

import sys

input = lambda: sys.stdin.readline().rstrip()
write = lambda x: sys.stdout.write(str(x) + "\n")

def travel(v, visited):
    # n= 5, 100000(2) - 1 =  11111(2)
    # 즉, 모든 곳을 방문했다면
    if visited == (1 << n) - 1:
        # 경로가 있을 경우
        if graph[v][0] : return graph[v][0]
        # 경로가 없을 경우
        return INF

    # dp
    if d[v][visited] != -1 : return d[v][visited]

    # 초깃값 세팅
    d[v][visited] = INF

    for next in range(1,n): # 모든 도시 순회
        # 다음 방문도시 != 현재 도시,i를 방문한적이 없는 경우,v-i 경로가 있을 경우
        if next != v and not (visited & (1 << next)) and graph[v][next]:
            # 점화식
            d[v][visited] = min(d[v][visited],
            travel(next, visited | (1 << next)) + graph[v][next])

    return d[v][visited]

# 항상 순회할 수 있는 경우만 주어짐
INF = int(1e9)
n = int(input())  # n은 16이하
d = [[-1] * (1 << n) for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]
print(travel(0,1))

외판원 순회는 n의 범위가 10개인지 16개인지에 따라 풀 수 있는 알고리즘이 다르다. 10개인 경우(외판원 순회2)는 완전탐색, 백트래킹 기법으로 비교적 쉽게 풀 수 있으나, 고작 도시가 6개 추가되는 외판원 순회 문제는 비트마스킹, dp, dfs 를 모두 활용하는 어려운 문제이다.

어느 출발지에서 출발해도 무관하다

어차피 한바퀴를 돌아서 제자리로 돌아오는 거니까, 출발지를 어디로 설정하든 상관없다.(나는 노드 0에서 출발했다.)

점화식

d[v : 현재 노드][A] = min(d[v][A], travel(next: 다음노드, A | next) + graph[v][i])

이미 방문한 곳을 나타내는 집합 A가 있다고 할 때, v는 현재 위치하고 있는 노드, next는 다음으로 방문할 노드이다.
v에서 next로 간다면, A에 next를 추가해주어야하기 때문에 A | u를 해준다.

비트마스크 기법

파이썬에는 set이라는 기본 자료구조가 있지만, 비트마스크 기법을 통해 방문기록을 나타내는 것이 더 효율적이기 때문에 비트마크스 기법을 사용했다.

111001(2) -> 0,3,4,5번 노드를 방문했다.

시간 복잡도

방문 여부 집합은 방문 여부 0과 1을 담기 때문에 2^n개의 상태를 가질 수 있고,
2^n 크기의 visit의 경우를 모두 한번씩 방문했다고 치면 O(2^n)
부분 문제에서 n번의 도시를 모두 loof를 돌리느까 O(N)
따라서, O(n * 2^n)의 시간 복잡도를 갖는다.

O(n^2 * 2^n)라고 합니다.. 좀 더 공부하고 수정하도록하겠습니다..