취미로 코딩하기

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

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

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

2098번 문제와 그 풀이방법은 같다. 거리를 실수값으로 미리 전처리해 문제를 해결하자.

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

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

int N;
int x[16], y[16];
double dist[16][16];
double dp[65536][16];
bool visited[65536];

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

					if (!visited[cur ^ idx]) {
						visited[cur ^ idx] = 1;
						que.push(cur ^ idx);
					}
				}
			}

		}
	}
}

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

	cout << fixed;
	cout.precision(10);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> x[i] >> y[i];
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int dx = x[i] - x[j], dy = y[i] - y[j];
			dist[i][j] = dist[j][i] = sqrt(dx * dx + dy * dy);
		}
	}

	bfs();

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

	cout << ans - 1;
}