Search

외판원 순회

Created
2021/03/23 01:58
문제 번호
2098
카테고리
DP
비트마스킹

Memo

TSP는 대표적인 NP-Hard 문제로, 시간 복잡도는 O(n!)O(n!)
nn값이 1515이상이면 11조 이상의 단위로 올라가버림 → 현 문제에서 주어진 최대 nn값인 16에 대해서는 풀지 못함
일반적인 시간 복잡도로는 풀지 못하지만, 순회는 해야하기 때문에 톱니바퀴 문제가 떠오름 (14891번) → 해당 풀이는 순회를 위해 DFS비트마스킹으로 풀어서 공간 복잡도 및 시간 복잡도를 많이 줄여서 풀었었음
방문 상태를 비트로 표현하면 되는데, nn이 최대 1616이므로 4바이트 내의 자료 형으로 충분히 커버 가능
비트를 이용하면 1~4까지 노드가 있을 때 아래와 같이 방문 노드를 표현할 수 있음
00010001
00100010
01000100
10001000
→ 위에서 모든 노드 방문은 11111111로 표현되며, 이는 2412^4 - 1과 같음
→ 최대 2162^{16}만큼의 연산량이 필요하기 때문에 비트마스킹 연산에 대해서만 O(2n)O(2^n)로 표기 가능하고, 모든 노드 방문은 2n12^{n} - 1로 표현할 수 있음
방문 상태 이용만으로 충분한가에 대한 고민을 하게 됨 → 이대로 돌리면 여전히 브루트포스와 다를 것이 없음 (정답이 나오지 않음)
방문 상태현재 노드 에 대한 최소 비용이 여러 정답 속에서 중복될 수도 있으므로, 방문 상태현재 노드에 대한 최소 비용을 유지할 수 있도록 Memoization 해야함 → 해주지 않으면 시간 초과 가능성이 다분해보임
각 노드에 대한 방문 상태이므로 O(n)O(n)이 추가적으로 요구됨
비트마스킹과 각 노드에 대한 연산이 O(n×2n)O(n \times 2^n)으로 표현되고, nn1616이라고 해도 연산량 내에 해당됨 → DFS 까지 고려하면 O(n2×2n)O(n^2 \times 2^n)이 되는데 역시나 연산량 내에 해당함
한 노드를 잡고 정답을 여럿 찾았을 경우, 다른 노드에 대해서도 DFS를 돌려야 하는가? → 그렇지 않음 한 노드에서 나온 정답이 곧 여러 정답과 중복됨 (TSP 경로의 성질)
11이라는 노드를 시작점으로 잡아서 찾은 여러 정답 중 123411 → 2 → 3 → 4 → 1가 하나의 해일 때, 123411→ 2→ 3 → 4 → 1라는 답이나 22라는 노드를 시작점으로 잡아서 찾은 234122 → 3→ 4→ 1 → 2나 비용은 동일하다는 것을 알 수 있음
재귀 구조만 잘 잡으면 됨
→ 방문 하지 않았고, 방문이 가능한 (비용이 있는) 경우 방문 비용 + 재귀 호출
→ 이에 따른 재귀 호출의 반환 값은 비용이 되어야 함
→ 최종적으로 원하는 비용 값은 최소 값이므로 재귀 호출로 만든 Sub Problem의 반환 값도 최소 값이어야 함 (즉, 최소 값을 찾을 수 있는 연산이 포함되어야 하는 것)
→ 이렇게 찾아진 Sub Problem의 최소 값도 Memoization에 기록 되어야 함
방문 상태를 나타내는 노드가 2n2^n만큼 존재함 → 인덱스 11부터 두고 사용하는 것보단 최대한 당겨서 00으로 맞추는 것이 60006000KB 정도의 메모리를 아낄 수 있음
입력으로 받는 비용은 최대 16×1616 \times 16개만 있으면 됨 → 인덱스 11부터 두고 사용하는 것보단 최대한 당겨 00으로 맞추는 것이 200200KB 정도의 메모리를 아낄 수 있음

Code

제출 날짜

@2/24/2021

메모리

6436 KB

시간

28 ms
#include <algorithm> #include <iostream> #include <vector> int g_n; int g_ans; std::vector<std::vector<int>> g_cost; std::vector<std::vector<int>> g_dp; void pre_setting(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } void input_action(void) { std::cin >> g_n; g_cost = std::vector<std::vector<int>>(g_n, std::vector<int>(g_n, 0)); g_dp = std::vector<std::vector<int>>(g_n, std::vector<int>(1 << g_n, 0)); for (int i = 0; i < g_n; i++) for (int j = 0; j < g_n; j++) std::cin >> g_cost[i][j]; } int tsp(int n, int m) { if ((m == (1 << g_n) - 1) && g_cost[n][0]) return (g_cost[n][0]); if (g_dp[n][m]) return (g_dp[n][m]); g_dp[n][m] = 1000000000; for (int i = 0; i < g_n; i++) if (!(m & (1 << i)) && g_cost[n][i]) g_dp[n][m] = std::min(g_dp[n][m], g_cost[n][i] + tsp(i, m | 1 << i)); return (g_dp[n][m]); } void logic(void) { g_ans = tsp(0, 1); } void output_action(void) { std::cout << g_ans; } void solution(void) { input_action(); logic(); output_action(); } int main(void) { pre_setting(); solution(); return (0); }
C++