icpc.me 2098 - CyberFlower Algorithm

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

외판원 순회 문제입니다. 문제 설명에도 나와 있지만 TSP(Traveling Salesman Problem) 이라고 하여 굉장히 유명한 문제입니다.

시작 여행지만 지정해 준다면 우리는 DP를 이용하여 tsp를 구할 수 있습니다.

memoization을 할 배열은 [가장 마지막으로 방문한 노드][지금까지 방문한 노드의 정보] 형식을 갖습니다. (따라서 우리는 [가장 마지막으로 방문한 노드][모든 점을 방문]+distance[가장 마지막으로 방문한 노드][시작 노드] 의 최솟값을 구하면 됩니다.)

n이 16 이하이기 때문에 지금까지 방문한 노드의 정보를 bitmask를 이용하여 16자리 이진수 형태로 나타낼 수 있습니다. int 자료형이 31자리(부호 bit 제외) 인걸 감안하면 int형으로 나타내면 충분합니다.

(TSP는 복잡도가 $ n^2\times 2^n $ 인 NP problem 중에 하나로, 문제로 나온다면 이 문제처럼 n이 매우 작을 수 밖에 없습니다. 새로운 TSP 알고리즘이 나오거나 휴리스틱 문제가 아닌 이상 말입니다.)

이제 점화식을 살펴볼까요? 점화식은 간단합니다.

$ memo[x][vst]=min(memo[x][vst],distance[x][nxt]+memo[nxt][vst^(1«nxt]) $

의 형식을 갖습니다. 물론 nxt는 아직 방문하지 않은 점이여야만 합니다.

우리는 이제 시작점을 다르게 하면서 그 중에서 가장 작은 tsp를 구하는 방식으로 정답을 찾을 수 있습니다. 이렇게 하면 시간복잡도가 $ O(n^3\times2^n) $ 이 되겠네요.

아까 말한것과 다릅니다. 여기서, 발상을 조금만 더 전환한다면 아까 말한 복잡도로 시간을 줄이는 것이 가능해집니다.

외판원 순회에서는 시작 노드가 어디든지 딱히 상관이 없습니다. 어차피 우리가 구하는 것은 거리가 가장 짧은 원 모양의 경로를 구하는 것이기 때문이죠. 1에서 시작하든, 2에서 시작하든 결국 찾게 되는 경로는 동일할 겁니다.

끝났습니다. 0에서 출발하도록 tsp(0)을 출력해주면 정답이 됩니다.

참고로, unsigned int 배열에서 -1로 memset을 하게 되면 int형으로 형변환시 INT_MAX와 동일한 값을 가지게 됩니다.

#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
const int SZ=18;
unsigned int memo[SZ][1<<SZ];
int graph[SZ][SZ];
int n;
int tsp(int stt){
	memset(memo,-1,sizeof(memo));
	memo[stt][1<<stt]=0;
	for(int i=1<<stt;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(!(i&(1<<j))) continue;
			for(int k=0;k<n;k++){
				if(i&(1<<k)) continue;
				if(memo[j][i]<INF && graph[j][k] && memo[k][(i^(1<<k))]>memo[j][i]+graph[j][k]) memo[k][(i^(1<<k))]=memo[j][i]+graph[j][k];
			}
		}
	}
	int mn=INF;
	for(int i=0;i<n;i++){
		if(i==stt) continue;
		if(graph[i][stt] && memo[i][(1<<n)-1]<INF) mn=min(mn,(int)memo[i][(1<<n)-1]+graph[i][stt]);
	}
	return mn;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++) cin>>graph[i][j];
	}
	cout<<tsp(0);
	return 0;
}

백준 2098 외판원 순회