[동적 계획법 3 단계] 백준 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로 가기 위한 비용을 나타낸다.

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

출력

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

 

모든 정점을 거치는 순회이므로 최단 경로라면 0에서 출발해서 0으로 돌아오든 1에서 출발해서 1로 돌아오든 같음.

따라서 0에서 출발로 지정한다.

 

visit처리를 위해서 visit 배열을 따로 사용할 수 있지만 그렇게 풀 수 없는 문제이기 때문에 비트마스킹을 통해 visit처리를 해준다.

0000000..00 (16자리)에서 1번째 자리가 1이면 0번 정점을 지나간 것을 의미 

따라서 0, 1에서 출발하고

만약 경로를 타고 이동하다가 최단 거리가 구해진 다음 정점까지 거리가 있다면 그대로 반환.

그리고 만약 모든 정점을 다 돌았을 경우 visited == (1 << N) -1 (정점이 2개로 생각해보면 1 << N 은 100이므로 -1을 해줘야 11)

최종 도착 지점 정점으로 부터 다시 0으로 돌아가는 경로가 있으면 그 값을 반환 없으면 무한대를 반환한다. (최소 경로 설정을 위해)

그리고 현재 지점에서 visited를 방문했을 때 앞으로 모든 정점을 순회하는데 비용이 D[current][visited]라고 하면 

INF로 두고 탐색을 진행한다.

방문하지 않은 지점에 대해서 visited & (1 << i) 가 true면 이미 그 비트가 찍혀있는 것이므로 방문한 것.

다음 탐색으로 나가면서 최솟값을 D[current][visited]에 저장하면 됨. 물론 arr[current][i]가 0이 아닐때(경로가 있을 때)

 

 

#include <iostream>
#include <vector>
#include<string.h>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;

const int INF = 987654321;
int N;
int arr[16][16];
int D[16][1<<16];

int tsp(int current, int visited)
{
	if (D[current][visited] != -1)
		return D[current][visited];

	if (visited == (1 << N) - 1)
	{
		if (arr[current][0])
			return arr[current][0];
		else
			return INF;
	}

	D[current][visited] = INF;
	for (int i = 0; i < N; i++)
	{
		if (arr[current][i] && !(visited & (1 << i)))
		{
			int visit = visited | (1 << i);
			D[current][visited] = min(D[current][visited], tsp(i, visit) + arr[current][i]);
		}
	}
	return D[current][visited];
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
		}
	}
	memset(D, -1, sizeof(D));
	cout << tsp(0, 1) << '\n';
	
}