컴퓨터 사이언스/1고리즘
백준 2098 : 외판원 순회
저세상 개발자
2021. 9. 6. 02:02
https://www.acmicpc.net/problem/2098
외판원 순회 문제(TSP, Traveling Salesman Problem)다.
최단거리 문제이지만 모든 노드를 방문해야 하므로 다익스트라나 플로이드워셜 등의 일반적인 그래프 최단거리 알고리즘은 사용하지 못하고 비트마스킹과 탑다운 DP로 해결 가능하다.
외판원 순회 문제 해결은 아래 블로그를 보고 참고했다. (비스마스킹, 탑다운 DP)
https://yabmoons.tistory.com/358
#include <iostream>
#define min(a,b) a<b?a:b
using namespace std;
int n;
int w[16][16];
int cost[16][1 << 16];
int ans_bit;
int dfs(int cur, int cur_bit) {
if (cur_bit == ans_bit) {
if (!w[cur][0]) return 1e8;
return w[cur][0];
}
if (cost[cur][cur_bit]) return cost[cur][cur_bit];
cost[cur][cur_bit] = 1e8;
for (int i = 0; i < n; i++) {
if (!w[cur][i]) continue;
if (cur_bit & 1 << i) continue;
cost[cur][cur_bit] = min(cost[cur][cur_bit], w[cur][i] + dfs(i, cur_bit | 1 << i));
}
return cost[cur][cur_bit];
}
void solution() {
cin >> n;
ans_bit = (1 << n) - 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> w[i][j];
}
}
cout << dfs(0, 1);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solution();
return 0;
}
메모리: 6116 kb | 시간: 32 kb |