[G1] 백준 16991번 외판원 순회 3 C++ 비트마스킹, 다이나믹 프로그래밍, 외판원 순회 문제

리뷰

 

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

간선의 가중치가 실수인 외판원 순회 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 도시의 수를 저장할 변수
• Pos : 도시의 좌표를 정의할 구조체
• poses : 도시의 좌표들을 저장할 Pos타입 배열
• Edge : 간선 정보를 정의할 구조체
• edges : 간선 정보를 저장할 Edge타입 벡터 배열
• dp : 방문 최소값을 저장할 2차원 배열

 

함수

1. get_dist

double get_dist(const Pos& pos1, const Pos& pos2) {
	return sqrt(pow(pos1.x - pos2.x, 2) + pow(pos1.y - pos2.y, 2));
}

 

두 좌표 사이의 거리를 구하기 위한 함수

 

2. dfs

double dfs(int mask, int cur) {
	if (mask == (1 << n) - 1) {
		double dist_to_start = get_dist(poses[cur], poses[1]);
		return dp[mask][cur] = dist_to_start;
	}

	if (dp[mask][cur] != -1.0f) return dp[mask][cur];

	dp[mask][cur] = 2e9;
	for (const Edge& edge : edges[cur]) {
		if (!(mask & (1 << edge.nn - 1))) {
			dp[mask][cur] = min(dp[mask][cur], dfs(mask | (1 << edge.nn - 1), edge.nn) + edge.nv);
		}
	}

	return dp[mask][cur];
}

 

모든 도시를 방문하고 원점으로 돌아오는 최소값을 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n개의 도시 좌표 정보를 입력 받아 poses배열에 저장해 준다.
2. 각 도시간 거리 정보를 get_dist함수로 구한 뒤 인접 리스트 edges에 양방향 간선으로 저장해 준다.
3. dp배열의 초기값을 -1.0으로 저장하여 미방문을 표시해 준다.
4. dfs함수에 1번 노드부터 방문함을 표시해 주고 재귀를 통해 dp배열을 최신화 해준다.
5. dfs함수는 현재까지의 방문 정보 mask와 현재 위치한 도시의 번호 cur을 매개변수로 전달 받는다.
6. 첫번째 기저 조건으로 모든 도시에 방문한 경우 현재 도시에서 1번 도시까지의 거리를 get_dist로 구한 뒤 dp값을 갱신 후 해당 값을 리턴해 준다.
7. 두번째 기저 조건으로 이미 최적값이 채워진 도시인 경우 그 값을 바로 리턴해 준다.
8. 두 기저 조건에 해당하지 않는 경우 dp[mask][cur]을 매우 큰 값으로 초기화 해준다.
9. cur의 인접 리스트를 순회하며 아직 방문하지 않은 경우 방문을 진행해 준다.
10. dp[mask][cur]을 dfs함수를 통해 다음 도시를 방문한 리턴 값 + 간선의 가중치 중 작은 값으로 갱신해 준다.
11. 모든 인접 리스트를 순회한 뒤 dp[mask][cur]에 저장된 값을 리턴해 준다.
12. dfs함수의 최종 리턴값을 출력해 준다.

 

트러블 슈팅

1. dfs함수를 그대로 호출해 주니 소숫점 아랫자리가 뒤죽 박죽이였다. 이대로 제출하니 Fail을 받았다.
2. cout << fixed, cout.precision을 통해 소숫점 아래 자리를 고정으로 출력해 주어 AC를 받았다.

 

참고 사항

1. 도시의 번호가 1-based-indexing이므로 방문 여부나 매개변수 전달 시 0-based-indexing처리 후 전달해 주었다.
2. fixed, precision을 통해 소숫점 자리를 고정으로 출력해 주었다.

 

정답 코드

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

const int N = 17;
int n;
struct Pos {
	int x, y;
};
Pos poses[N];
struct Edge {
	int nn;
	double nv;
};
vector<Edge> edges[N];
double dp[1 << N][N];

double get_dist(const Pos& pos1, const Pos& pos2) {
	return sqrt(pow(pos1.x - pos2.x, 2) + pow(pos1.y - pos2.y, 2));
}

double dfs(int mask, int cur) {
	if (mask == (1 << n) - 1) {
		double dist_to_start = get_dist(poses[cur], poses[1]);
		return dp[mask][cur] = dist_to_start;
	}

	if (dp[mask][cur] != -1.0f) return dp[mask][cur];

	dp[mask][cur] = 2e9;
	for (const Edge& edge : edges[cur]) {
		if (!(mask & (1 << edge.nn - 1))) {
			dp[mask][cur] = min(dp[mask][cur], dfs(mask | (1 << edge.nn - 1), edge.nn) + edge.nv);
		}
	}

	return dp[mask][cur];
}

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y;
		poses[i] = { x, y };
	}

	for (int i = 1; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			const Pos& pos1 = poses[i];
			const Pos& pos2 = poses[j];
			double dist = get_dist(pos1, pos2);

			edges[i].push_back({ j, dist });
			edges[j].push_back({ i, dist });
		}
	}

	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < N; j++) {
			dp[i][j] = -1.0f;
		}
	}

	cout << fixed;
	cout.precision(10);
	cout << dfs(1, 1);
}