[C/C++] 백준 외판원 순회 문제 / 백준 2098번, 백준 10971번, 백준 16991번

✏️ 문제 링크

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

2098번: 외판원 순회

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

기본적인 외판원 순회 알고리즘을 구현하는 문제입니다.

외판원 순회 문제는 영어로 TSP라고 불리고, 컴퓨터 과학 분야에서 가장 중요하게 취급되는 문제 중 하나입니다.

주로 DP방식을 이용해서 풀고 비트필드를 이용해서 문제를 접근합니다.

처음엔 이해하는데 어려울 수 있지만 직접 손으로 풀어보신다면 아마도 이해가 되실 것 같습니다.

TSP는 기본적인 틀이 짜져있기 때문에 이해가 안 되신다면 외우는 것도 추천드립니다.

 

✏️ 문제 코드

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

int W[16][16];
int INF = 1000000 * 16 + 1;
int N;
int D[16][1 << 16];
int tsp(int c, int v);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cin >> W[i][j];
	}
	cout << tsp(0, 1);
}

int tsp(int c, int v) {

	if (v == (1 << N) - 1)
		return W[c][0] == 0 ? INF : W[c][0];

	if (D[c][v] != 0)
		return D[c][v];
	int min_val = INF;
	for (int i = 0; i < N; i++) {
		if ((v & (1 << i)) == 0 && W[c][i] != 0) {
			min_val = min(min_val, tsp(i, (v | (1 << i))) + W[c][i]);
		}

	}
	D[c][v] = min_val;
	return D[c][v];
}

 

 

 

 

 

✏️ 문제 링크

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

10971번: 외판원 순회 2

 

 

✏️ 문제 링크

 

 

✏️ 문제 코드

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

#define MAX 99999999
int W[16][16];
int D[16][1 << 16];
int N;
int tsp(int start, int visit);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cin >> W[i][j];
	}
	cout << tsp(0, 1);
}
int tsp(int start, int visit) {
	if (visit == ((1 << N) - 1))
		return W[start][0] == 0 ? MAX : W[start][0];

	if (D[start][visit])
		return D[start][visit];

	int min_val = MAX;
	for (int i = 1; i < N; i++) {
		if ((visit & (1 << i)) == 0 && W[start][i] != 0)
			min_val = min(min_val, tsp(i, visit | (1 << i)) + W[start][i]);
	}
	D[start][visit] = min_val;
	return D[start][visit];
}

 

 

 

 

 

✏️ 문제 링크

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

16991번: 외판원 순회 3

 

 

✏️ 문제 설명

 

 

 

✏️ 문제 코드

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

#define MAX 99999999.999999
double W[16][16];
double D[16][1 << 16];
int N;
typedef pair<int, int>cur;
cur arr[16];
double tsp(int start, int visit);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> arr[i].first >> arr[i].second;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j)
				continue;
			if (W[i][j])
				continue;
			else {
				int a = arr[j].second - arr[i].second;
				int b = arr[j].first - arr[i].first;
				W[i][j] = sqrt(a * a + b * b);
			}
		}
	}

	double result = tsp(0, 1);
	cout << fixed;
	cout << result;
}
double tsp(int start, int visit) {
	if (visit == ((1 << N) - 1))
		return W[start][0];

	if (D[start][visit])
		return D[start][visit];

	double min_val = MAX;
	for (int i = 1; i < N; i++) {
		if ((visit & (1 << i)) == 0&&W[start][i]!=0)
			min_val = min(min_val, tsp(i, visit | (1 << i)) + W[start][i]);
	}
	D[start][visit] = min_val;
	return D[start][visit];
}

 

 

 

✏️ 배운 점

비트필드는 조금 낯선 부분이였는데 생각보다 어렵지도 않고, 비트수를 이용해서 방문여부를 표시할 수 있다

평소에는 소수점 자리출력을 할 때 cout.precision()으로 자릿수를 고정하였는데

기본적인 6자리 출력은 cout.fixed()로도 할 수 있다