취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2098번 문제인 외판원 순회이다.
문제는 아래 링크를 확인하자.

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

TSP 문제는 다양한 풀이가 잘 알려져있는 문제이다. 여기서는 비트최적화 DP로 문제를 해결해보자.

지금까지 방문한 도시들의 집합 S와 현재 방문중인 도시 C의 순서쌍 (S,C)를 하나의 노드로 생각하자. 그리고 0번 도시에소 출발해 S의 도시들을 전부 방문한 상태로 C 도시에 머무르는 최소 거리를 dist((S,C))로 쓰기로 하자.

dist((S,C))는 "dist((S에서 도시 C이 빠진 집합 S', S'의 원소 C')) + (C'에서 C까지의 거리)"의 최솟값으로 나타낼 수 있다는 점을 관찰해 dp를 진행해보자.

여기서 집합 S는 도시의 수가 충분히 적다면 비트를 이용해 하나의 정수로 표현이 가능하다는 점을 적극 이용하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int N;
int dist[16][16];
int dp[65536][16];
bool visited[65536];

void bfs() {
	visited[0] = visited[1] = 1;
	dp[1][0] = 1;
	queue<int> que;
	que.push(1);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (int s = 0; s < N; s++) {
			if (dp[cur][s] == 0) continue;
			int sidx = (1 << s);
			if ((cur & sidx) == 0) continue;
			for (int e = 0; e < N; e++) {
				int eidx = (1 << e);
				if (cur & eidx) continue;
				if (dist[s][e] == 0) continue;
				
				if (dp[cur ^ eidx][e] == 0) dp[cur ^ eidx][e] = dp[cur][s] + dist[s][e];
				else dp[cur ^ eidx][e] = min(dp[cur ^ eidx][e], dp[cur][s] + dist[s][e]);
				if (!visited[cur ^ eidx]) {
					visited[cur ^ eidx] = 1;
					que.push(cur ^ eidx);
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> dist[r][c];
	}

	bfs();

	int ans = 1000000007;
	int MX = (1 << N) - 1;
	for (int i = 0; i < N; i++) {
		if (dp[MX][i] == 0) continue;
		if (dist[i][0] == 0) continue;
		ans = min(ans, dp[MX][i] + dist[i][0]);
	}

	cout << ans - 1;
}