[백준] 2098 외판원 순회 + 이해하기 쉬운 외판원 순회 설명

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

 

 

#include <bits/stdc++.h>
using namespace std;
int n, arr[16][16], dp[16][1 << 16], MAX = 1987654321;
//arr : 지도
//dp[i][j] : 현재 위치 i 일때, 이미 방문한 도시를 비트마스크로 표시 (사이즈는 1<<16)
int tsp(int cur, int visited) {  //현재위치 cur, 방문한도시 visited
	if (dp[cur][visited])
    	return dp[cur][visited]; //만약 이미 저장된값 memorized , 존재하면 그대로 반환

	if (visited == (1 << n) - 1) { //만약 모든 도시를 방문했다면 (111...111 == (1<<n)-1)
		if (arr[cur][0])//마지막 돌아오는 길도 있어야 함
			return arr[cur][0];
		return MAX; //없으면
	}
	dp[cur][visited] = MAX; //현재 위치에 대해 갱신할것
	for (int i = 0; i < n; i++) {
		if (visited & (1 << i) || !arr[cur][i])continue; //이미 방문했거나, 길이 없으면 continue
		dp[cur][visited] = min(dp[cur][visited], tsp(i, visited | (1 << i)) + arr[cur][i]);
        //이미 존재하는값과 tsp(i,visited|(1<<i))+ arr[cur][i] 중 비교, 작은값 갱신
	}
	return dp[cur][visited];
}
int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

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

DP를 이용한 문제입니다.

DP메모제이션을 사용해야하는 이유는, A에서 출발하던 B에서 출발하던,,,, CDE 를 지나가는 길은 하나로 정해져있기 때문입니다. 

 

 

 

라고 설명하고 아래에는 외판원 순회에 대해 쉽게 설명해 보겠습니다.

 

여러 지점을 한번씩 통과하면서 최저 비용으로 한바퀴 도는 방법은 단순합니다.

모든 지점을 직접 한번씩 돌아보면 됩니다. 

0에서 시작해서

0 1 2 3 0

0 1 3 2 0

0 3 1 2 0

0 3 2 1 0

0 2 1 3 0

0 2 3 1 0

이렇게 돌다가 가장 비용이 낮은도로가 답입니다.

하지만 지점의 수가 많아지면..... 이렇게 탐색을 하려면 시간이 최대 !n 번 걸리게 됩니다.

따라서 이렇게 모든 경우를 탐색할껀데... 좀 효율적으로 탐색하는 방법이 바로 DP 메모제이션을 이용한 방법입니다.

 

지점 ABCDEF가 있다고 할때...

A에서 시작해서 BCDEF를 돌기 위한 최저비용을 구하려면

    B에서 시작해서 C,D를 돌았을 때 E,F를 도는 비용 (A다음에 B,C,D를 방문했을때 ,,남은D->EF)....

    C에서 시작해서 BD를 돌았을 때, E,F를 도는 비용 (A 다음에 CBD를 방문했을때 D->EF).....

    이 둘의 비용을 비교한다 했을때,

 

이렇게 D에서 E와F를 방문하는 비용을 구할때 겹치게 됩니다.

한번만 구해서 어디다가 저장만 해놓으면, 이후에 다시 구할필요가 없기 때문에 더 빠릅니다.

 

따라서 2차원배열 dp[c][v]에 그 정보를 저장을 할껀데,  

c는 마지막으로 방문한 현재 위치 (D->EF)에서 D를 저장하고,

v에는 지금까지 방문한 도시들 (ABCD)를 저장을 할겁니다. 

 

이때 지금까지 방문한 도시를 저장할 때 비트마스크를 사용합니다. (n<=16)

 

   

 

 

#include <bits/stdc++.h>
using namespace std;
int n, arr[16][16], dp[16][1 << 16], MAX = 1987654321;
//arr : 지도
//dp[i][j] : 현재 위치 i 일때, 이미 방문한 도시를 비트마스크로 표시 (사이즈는 1<<16)
int tsp(int cur, int visited) {  //현재위치 cur, 방문한도시 visited
	if (dp[cur][visited])
    	return dp[cur][visited]; //만약 이미 저장된값 memorized , 존재하면 그대로 반환

	if (visited == (1 << n) - 1) { //만약 모든 도시를 방문했다면 (111...111 == (1<<n)-1)
		if (arr[cur][0])//마지막 돌아오는 길도 있어야 함
			return arr[cur][0];
		return MAX; //없으면
	}
	dp[cur][visited] = MAX; //현재 위치에 대해 갱신할것
	for (int i = 0; i < n; i++) {
		if (visited & (1 << i) || !arr[cur][i])continue; //이미 방문했거나, 길이 없으면 continue
		dp[cur][visited] = min(dp[cur][visited], tsp(i, visited | (1 << i)) + arr[cur][i]);
        //이미 존재하는값과 tsp(i,visited|(1<<i))+ arr[cur][i] 중 비교, 작은값 갱신
	}
	return dp[cur][visited];
}
int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

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

 

결국 중요한건 외판원 순회 알고리즘도 모든 정점을 탐색하는 효율적인 방법이라는겁니다.

따라서 재귀를 이용해 문제를 풀 수 있습니다.

만약 이미 저장된 값이 존재한다면 그 값을 반환하면 됩니다.

모든 정점을 방문했을때는 돌아오는 길이 있는지 확인합니다.