[BOJ] 2098번: 외판원 순회

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

TSP는 기본적으로 NP-hard 문제입니다.(즉 다항시간 알고리즘을 현재까지 찾지 못했고 또 찾을 가능성이 매우 희박합니다.) 임의의 경로를 택한 후 걸리는 시간을 더해나가는 식으로 답을 구하려고 한다면 O(N!)인데, N=16인 현 상황에서는 절대 시간내에 해결할 수 없습니다.

이 때 Dynamic Programming을 활용한다면 그나마 O(2^N * N^2)으로 시간복잡도를 떨굴 수 있습니다.

문제의 조건에 따라 cycle이 반드시 존재하고, 또 이러한 cycle은 시작점을 어디로 잡던지 최솟값이 일정하기 때문에 마을을 편의상 0~N-1번 마을로 둔다면 0번 마을에서 시작하는 것으로 고정해도 아무런 상관이 없습니다.

이 때 D[i][j] : i번째 마을을 j에 기록된 대로 거치고 마지막으로 방문했을 때 최소의 거리

라고 두겠습니다. 이 떄 i는 0~N-1이고 j는 0~2^N-1입니다.(즉, 이진수로 기록합니다.)

예를 들어

2

0 4

4 0 이라는 input에 대해

D[0][0] = -1

D[0][1] = 0 // 1은 이진수로 01. 즉 0번마을만을 거친 상황

D[0][2] = -1 // 2는 이진수로 10. 즉 1번마을만을 거친 상황

D[0][3] = -1 // 3은 이진수로 11. 즉 0, 1번마을만을 거친 상황

D[1][0] = -1

D[1][1] = -1

D[1][2] = -1

D[1][3] = 4

이 때 D[i][j] = j에서 임의의 1인 1비트를 제거한 상태에서 건너가는 거리로 갱신이 가능하며 O(N)이 필요합니다. D의 원소는 2^N * N이므로 시간복잡도가 O(2^N * N^2)입니다.

https://github.com/encrypted-def/BOJ/blob/master/2098.cpp