컴퓨터 사이언스/1고리즘

백준 2098 : 외판원 순회

저세상 개발자 2021. 9. 6. 02:02

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

 

2098번: 외판원 순회

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

 

외판원 순회 문제(TSP, Traveling Salesman Problem)다.

최단거리 문제이지만 모든 노드를 방문해야 하므로 다익스트라나 플로이드워셜 등의 일반적인 그래프 최단거리 알고리즘은 사용하지 못하고 비트마스킹과 탑다운 DP로 해결 가능하다.

 

외판원 순회 문제 해결은 아래 블로그를 보고 참고했다. (비스마스킹, 탑다운 DP)

https://yabmoons.tistory.com/358

 

[ 백준 2098 ] 외판원 순회 (C++)

백준의 외판원 순회(2098) 문제이다. [ 문제 바로가기 ] [ 문제풀이 ] 1) 도시의 갯수가 주어졌을 때, 임의의 한 도시에서 시작해서 모든 도시를 거쳐서 다시 시작 도시로 돌아올 때 드는   최소비용

yabmoons.tistory.com

 

#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