#2098 외판원 순회

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

2098번: 외판원 순회

 

외판원 순회는 세계일주 라고 생각하면 된다. 한국에서 출발하는데 가고싶은 나라가 프랑스 독일 영국이라면

한국에서 출발해서 어떻게 나라를 거쳐가서 돌아올때가 가장 경비가 저렴한지의 느낌으로 풀어주면 된다.

이 문제는 비트마스킹을 이용하여 메모이제이션을 활용한 dp문제이다.

 

만약 총 노드가 0,1,2,3 이렇게 4개가 주어지고 0에서 출발했을때 0으로 돌아올 경로의 경우의 수는

0-1-2-3, 0-1-3-2, 0-2-1-3, 0-2-3-1, 0-3-1-2, 0-3-2-1 이다.

 

인덱스 즉 노드의 방문이 다음과 같이 순서대로 거쳐가는것을 알 수 있다.

이제 메모를 활용해야 하는데

 

이 재귀의 상태를 그림으로 그려보면 다음과 같다.

 

먼저 재귀를 통한 탐색을 하게되면 자식노드가 없는 단말 노드까지 쭉 내려간다. 이따 단말노드가 처음으로 가는 경로 즉 arr[단말노드][0(시작노드)] 값이 0이 아니면 arr[단말노드][0(시작노드)]를 리턴해준다. 그러면 맨처음에는 memo[2][1+2+4=7]값은 기존memo[2][7](무한대값)과 이 arr[3][15]값중 min값인arr[3][15]를 선택하고 마찬가지로 memo[3][1+2+8]부분도 같은 방식으로 값이 설정된다. 그 후 memo[1][3]은 이제 자식노드인 memo[2][7] 과 memo[3][11] 중 min값을 선택하게 된다. 이와 같은 방식으로 나머지 노드들도  min값을 선택하게 된다.

 

또한 이 과정에서 메모이제이션을 활용하게 되는데 

이미구한  memo는 min값으로 구해줬는데 만약 memo가 구해진 상태라면 이미 구한 memo를 또 구해줄 필요가 있을까? 그럴필요가 없다. 그래서 memo가 값이 정해진다면 if(memo[노드][비트마스킹값]이 0 이상이라면 해당 값만 리턴을 해서 다시 하위노드로 함수를 호출하는 불필요한 함수호출 반복을 방지해준다.

 

소스코드

 

	// #2098 외판원순회
	#include <iostream>
	using namespace std;
	#include <cstring>
	#define endl '\n'
	int start, cnt;
	int memo[17][1 << 17];
	int arr[17][17];
	int n;
	int INF = 1000000000;
	int MIN(int a, int b) {
	return a < b ? a : b;
	}
	int dfs(int idx, int light) {
	//cout << " idx " <<idx<<" light "<< light << endl;//
	if (memo[idx][light] >= 0)return memo[idx][light];
	//종료조건
	if (light == (1 << n) - 1) {//모든 마을을 방문했을 경우
	if (arr[idx][start] != 0) {//시작 마을로 갈 수 있을 경우
	//cout << "true" << endl;
	//cout << endl;
	return arr[idx][start];
	}
	else {
	//cout << "false" << endl; cout << endl;
	return INF;//불가능하면 매우 큰 수로 리턴
	}
	}
	memo[idx][light] = INF;
	for (int i = 0; i < n; i++) {
	if ((light&1 << i)||arr[idx][i] == 0)continue;//방문 확인여부
	memo[idx][light] = MIN(memo[idx][light], dfs(i, light | 1<< i) + arr[idx][i]);
	}
	return memo[idx][light];
	}
	int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	cin >> n;
	int x = 1;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	cin >> arr[i][j];
	}
	}
	int result = INF;
	for (int i = 0; i < n; i++) {
	//cout << " start " << i << endl;//
	memset(memo, -1, sizeof(memo));
	start = i;
	result = MIN(result, dfs(i, 1 << i));
	}
	cout << result << endl;
	}

view raw [BOJ]2098.cpp hosted with ❤ by GitHub