문제

문제 링크

해설

• 외판원 문제는 대표적인 NP 완전 문제입니다. NP 완전 문제란, 다항 시간내에 최단 비용을 계산할 수 없다고 알려진 문제를 의미합니다.
  • 일반적으로 DP 등의 알고리즘을 활용하면, 최적해는 아니더라도 최적해에 근접한 근사치를 빠르고 효율적으로 찾을 수 있다고 알려져 있습니다.
• 하지만, 임의의 한 점에서 출발해서 최단 경로를 이용해 다시 제자리로 되돌아오는 외판원 문제의 경우에는 특별한 경우입니다.
  • 현재 도시 / 방문한 도시들의 집합 2가지를 상태로 하는 2차원 메모이제이션 집합을 이용해 DP를 활용하면 빠르게 최적해를 구할 수 있습니다.
  • 참고로 시간복잡도는 $2^N * N$입니다. 이는 입력 크기 N이 작은 경우(N <= 20)에는 충분히 계산 가능한 범위입니다.
• 입력 N이 최대 16까지 이므로 비트플래그를 이용해서 방문 여부를 확인할 것입니다.
  • 예를 들어, 3번 bit가 set인 경우, 3번 도시에 방문했다는 것이고
  • 7번 bit가 reset인 경우, 7번 도시에는 아직 방문하지 않았다는 것입니다.
  • DP[16][1 << 16] 라는 2차원 메모이제이션 집합을 정의할 것입니다.
• 모든 도시를 거쳐서 다시 원래 도시로 돌아왔다면, 모든 도시를 방문했을 것이며 N개의 bit가 모두 set 돼있을 것입니다. 이는 수식으로 (1 << N) - 1로 표현합니다.

for (int i = 0; i < N; ++i) {
	if (비트플래그 & (1 << i) || !dist[현재도시][i]) continue;
	DP[현재도시][비트플래그] = min(DP[현재도시][비트플래그], go(i, 비트플래그 | (1 << i)) + dist[현재도시][i]);
}

• 매 도시마다 0번 도시부터 N번 도시까지 검사합니다.
  • 이미 방문했거나 / 길이 없어서 갈 수 없는 도시라면 continue로 계산하지 않습니다.
• 방문표시는 OR 연산자를 이용해서 비트플래그 | (1 << i)로 합니다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, dist[16][16], DP[16][1 << 16];

int go(int here, int visited) {
	if (visited == (1 << N) - 1) return dist[here][0] ? dist[here][0] : 1e9;
	
	int& ret = DP[here][visited];
	if (~ret) return ret;
	
	ret = 1e9;
	for (int i = 0; i < N; ++i) {
		if (visited & (1 << i) || !dist[here][i]) continue;
		ret = min(ret, go(i, visited | (1 << i)) + dist[here][i]);
	}
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x)
			cin >> dist[y][x];

	memset(DP, -1, sizeof(DP));
	cout << go(0, 1);
}

결과