외판원 순회(DP, BitMask)

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

2098번: 외판원 순회

 

해밀턴 경로: 그래프의 모든 정점을 한 번씩만 방문하는 경로.

해밀턴 순환: 시작점과 끝점이 같은 해밀턴 경로, 해밀턴 순환을 구하는 문제는 NP문제에 속한다.

 

외판원 순회는 이러한 해밀턴 순환중 간선의 합이 최소가 되는 루트를 구하는 문제라고 볼 수 있다.

완전 탐색(브루트포스) 방법으로 값을 구할 수 있지만 그렇게 되면 n! 시간이 소요되므로(n개의 숫자에 대한 순열)

노드의 갯수가 10개 이하에서 시도할만한 방법이다.

 

해당 문제는 메모이제이션을 통한 다이나믹 프로그래밍과 비트마스크 방법을 같이 사용해야한다.

---

1. DP[cur][visited]의 위치에 경로의 최소값을 저장한다.

cur은 현재 노드, visited는 방문한 노드의 정보를 의미한다.

 

2. visited는 방문한 노드의 정보를 비트마스크 기법을 사용하여 저장한다.

비트마스크 특정 알고리즘이 아닌 테크닉으로써 정수를 이진수처럼 사용하는 방법이다.

bit 연산을 사용하므로 다른 자료구조보다 빠르고 간결하게 동작하기 때문에 불필요한 연산을 최소화 할 수 있다.

(2^16가지 경우의 수를 16bit로만 표현 가능)

예를 들면 16개의 노드가 있고 1, 3, 5번 노드를 방문했을때 visited는 다음과 같다.

visited = 0000 0000 0001 0101(2) = 21

 

3. 재귀 알고리즘은 현재 노드와 방문한 노드의 정보를 파라미터로 받는다.

현재 노드와 방문한 노드의 정보에 대한 최소경로값이 이미 저장되어있으면(메모이제이션) 그 값을 그대로 사용한다.

저장된 값이 없다면 현재 노드로부터 모든 노드(다음 노드)에 대하여 순회탐색을 실시한다.

DP[현재노드][방문상태] = min(DP[현재노드][방문상태], 현재노드->다음노드 값 + DP[다음노드][방문상태에서 다음 노드가 추가된 값])

---

visited의 경우의 수는 2^n가지, n개의 노드에 대해서 n개의 노드를 탐색하므로 시간복잡도는 O(n^2*2^n)

 

코드의 각 라인에 주석을 첨부해놓았으니 참고하면 알고리즘의 동작을 이해하는데 도움이 될 것이다.

 

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

int Size;
int Matrix[16][16];
int DP[16][1 << 16];

int solve(int cur, int visited)
{
	if (visited == (1 << Size) - 1)
	{
		// 노드를 전부 방문한 상태라면
		// 현재 노드에서 시작지점(0번째 노드)로 가야함
		if (Matrix[cur][0] == 0) return 16000001;
		else return Matrix[cur][0];
	}
	// DP[현재 지점][방문 상태]를 참조
	int& ret = DP[cur][visited];
	// 이미 값이 저장되어있으면 해당 값을 그대로 사용(다이나믹 프로그래밍)
	if (ret != -1) return ret;
	// 값이 없다면 계산해야함
	ret = 16000001;
	// 현재 노드로부터 모든 노드를 순회
	for (int next = 0; next < Size; next++)
	{
		// 갈 수 없는 경우는 바로 continue
		if (Matrix[cur][next] == 0) continue;
		// 방문 상태를 확인해서 이미 방문한 노드라면 continue
		if ((visited & (1 << next)) == (1 << next)) continue;
		// 아니라면 재귀를 통해서 현재 값과 비교하여 더 작은 값을 캐치
		// 재귀를 통해 전달되는 파라미터는 (다음 노드, 기존 방문상태에 다음 노드가 추가된 상태)
		// ret은 DP의 참조이므로 DP에 값이 저장되게 됨
		ret = min(ret, Matrix[cur][next] + solve(next, visited | 1 << next));
	}
	return ret;
}

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

	cin >> Size;

	for (int i = 0; i < Size; i++)
	{
		for (int j = 0; j < Size; j++)
		{
			cin >> Matrix[i][j];
		}
	}
	memset(DP, -1, sizeof(DP));
	cout << solve(0, 1) << '\n';
}

비트 연산을 활용하는 법을 유심히 보자.

11: if (visited == (1 << Size) - 1)

30: if ((visited & (1 << next)) == (1 << next)) continue;

34: ret = min(ret, Matrix[cur][next] + solve(next, visited | 1 << next));