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

문제

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

2098번: 외판원 순회

1.완전 탐색

처음엔 [BOJ 10971] 외판원 순회2 문제와 동일하게 모든 도시를 각각 출발지로 하여 N번 순회를 수행했지만 시간 초과가 발생했다.  

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

#define INF 987654321

int N, edge[17][17], ans = INF, start;

void init() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> edge[i][j];
			if (i == j) continue;
		}
	}
}

void travel(int cur, int cost, int visited, int cnt) {
	if (cur == start && cost != 0) {
		ans = ans > cost ? cost : ans;
		return;
	} 
	for (int next = 1; next <= N; next++) {
		if (!edge[cur][next]) continue;
		if (cnt != N - 1 && next == start) continue;
		if(next != start && (visited & (1 << next)) != 0) continue;
		travel(next, cost + edge[cur][next], visited | (1 << next), cnt + 1);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	init();
	for (int i = 1; i <= N; i++) {
		start = i;
		travel(i, 0, 1 << i, 0);
	}
	cout << ans;
	return 0;
}

 

2.순회 한번만 수행

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

직접 위 예제를 완전 탐색으로 N번 순회를 수행해본 결과 출발 도시를 바꿔가며 N번 순회를 수행할 필요가 없다는 것을 깨달았다.

---

0 -> 2 -> 1 -> 3 -> 0

2 -> 1 -> 3 -> 0 -> 2

위 경우 0->2의 순서만 달라지는 것이기 때문에 두 경우는 동일한 것은 자명한 사실이었던 것이다...

이에 따라 순회를 한번만 수행하도록 코드를 수정해 주었다.

 

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

#define INF 987654321

int N, edge[17][17], ans = INF, start;

void init() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> edge[i][j];
			if (i == j) continue;
		}
	}
}

void travel(int cur, int cost, int visited, int cnt) {
	if (cur == 1 && cost != 0) {
		ans = ans > cost ? cost : ans;
		return;
	} 
	for (int next = 1; next <= N; next++) {
		if (!edge[cur][next]) continue;
		if (cnt != N - 1 && next == 1) continue;
		if(next != 1 && (visited & (1 << next)) != 0) continue;
		travel(next, cost + edge[cur][next], visited | (1 << next), cnt + 1);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	init();
	travel(1, 0, 1 << 1, 0);
	cout << ans;
	return 0;
}

외판원 순회2번 문제로 비교해본 결과 확실히 속도가 향상되었다.

 

---

하지만 본 문제의 경우 위 처럼 로직을 수정해 주어도 여전히 시간 초과가 발생했다.

 

외판원 순회2 문제의 경우 노드의 개수가 최대 10개이기 때문에 완전 탐색으로 해결 가능하나 본 문제의 경우 노드가 최대 16개이기 때문에 완전 탐색으로는 시간 초과가 발생했다.

 

따라서 본 문제의 경우 DP와 비트마스킹을 사용하여 해결해주었다.

3.DP + 비트마스킹

DP memoization을 통해 동일한 계산에 대한 반복 연산을 줄이고 비트마스킹을 사용하여 방문한 도시들의 상태를 나타내었다.

즉, dp[3][11](=dp[3][1011]) = 15은 현재 3번 도시를 0, 1번 도시를 거쳐 방문했고 아직 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아가는 최소 비용은 15라는 의미이다.

 

코드와 예시를 통해 어떻게 반복 연산을 방지해주는지 살펴 보자

 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
// 비트마스킹 + DP
#define INF 1987654321
int N, edge[16][16];
// dp[k][state] : k번째 마을, state: 방문했던 도시들을 2진법으로 표시.
int dp[16][1 << 16];

int TSP(int cur, int visited) {
	int& ret = dp[cur][visited];
	if (ret != -1)
		return ret;
	// 모든 마을 방문했는가
	if (visited == (1 << N) - 1) {
		// current -> 0 이동 가능한지 
		if (edge[cur][0] != 0)
			return edge[cur][0];
		// 가능하지 않으면
		return INF;
	}
	ret = INF;
	for (int next = 0; next < N; ++next) {
		if (!edge[cur][next]) continue; //cur -> next로 간선이 없으면 pass
		if (visited & (1 << next)) continue; //next가 이미 방문됐으면 pass
		ret = min(ret, TSP(next, visited | (1 << next)) + edge[cur][next]);
	}
	return ret;
}

void init() {
	cin >> N;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> edge[i][j];
	memset(dp, -1, sizeof(dp));
}

int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	init();
	cout << TSP(0, 1) << '\n';

	return 0;
}

위 예제를 통해 살펴보면

0 -> 1 -> 3 -> 2 -> 0 을 순회하면서 dp[2][1111] = 6이 저장 된다.

이는 0, 1, 3번 도시를 방문한 뒤 2번 도시를 방문했을 때 다시 0으로 돌아가는 모든 경로 중 6이 최단 거리라는 것을 의미하게 되는 것이다.

이에 따라 0 -> 3 -> 1 -> 2 -> 0 을 순회할 때 2->0으로 가는 비용은 다시 구할 필요가 없게 되는 것이다.