백준 2098 TSP

백준 2098<-클릭
유명한 TSP문제이다. TSP문제는 DP와 DFS로 해결 가능한데 DP로 해결하였다.
DP와 더불어 방문 예정 도시를 표시하기 위해 비트 마스크를 사용하였다. 이 문제에서 도시의 개수는 16개로 제한지만 계산 중 오버플로우를 방지하기 위해 17자리 비트를 사용하였다.

변수 설정

TSP에 설명하기 앞서 변수는 다음과 같이 설정하였다.
A: 앞으로 방문해야하는 도시 집합(bit)
vi: 현재 위치한 도시(bit)
i: 현재 위치한 도시(int)
j: 다음에 방문할 도시(int)
A_vj:A에서 vj도시를 제외한 도시 집합(bit)

TSP 아이디어

tsp를 dp로 해결할 때의 기본적인 아이디어는 다음과 같다

• dp함수에 현재 나의 위치와 앞으로 방문할 도시의 집합을 넣는다.
  
  
• dp함수는 리턴 값은 다음으로 정한다.
  현재 나의 위치 → 앞으로 방문할 도시의 집합을 모두 방문→ 1번 도시 경로의 최소 비용
  
  
• 중복 연산을 막기 위해 메모이제이션을 수행한다.
  
  
• 방문할 도시가 남아 있으면 for문을 돌며 하나씩 고른다. 현재 위치를 i, 고른 도시를 j라고 하면
  min(W[i][j]+dp[j][A_vj]). 단 W[i][j]가 앞에 있는 최소보다 크다면 굳이 dp를 수행하지 말고 continue해준다.
  
  
• 방문할 도시가 없다면 W[i][1]리턴 (0일 경우는 INF리턴)

코드

github

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<bitset>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 987654321
int N;
int map[17][17];
int dp[17][1 << 16];
int dp_f(bitset<17>vi, bitset<17> A);
int min_cost = INF;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input/2098_input.txt", "r", stdin);
	cin >> N;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	bitset<17> first((1<<N)-2);
	bitset<17> va(0b1);
	cout << dp_f(va, first) << endl;
	return 0;
}

int dp_f(bitset<17>vi, bitset<17> A) {
	int minimum = INF;
	int i;
	for (int k = 0; k < N; k++) {
		if (vi.test(k)) {
			i = k + 1;
		}
	}
	int ret = dp[i][A.to_ulong()];
	if (ret != -1) return ret;
	if (A == 0) { //마지막 방문
		if (map[i][1] != 0) {
			return map[i][1];
		}
		return INF;
	}
	
	for (int j = 0; j < N; j++) {
		if (A.test(j)) {
			bitset<17>vj(1 << j);
			bitset<17> A_vj(A & ~vj);
			if (map[i][j + 1] > minimum) continue;
			int rst = dp_f(vj, A_vj);
			if(map[i][j+1]!=0)minimum = min(minimum, map[i][j+1]+ rst);
		}
	}
	dp[i][A.to_ulong()] = minimum;
	return minimum;
}

참고

1. first가 (1<<N)-2 인 부분을 볼 수 있는데 N자리 1111...10이다. 1번 도시에서 출발하여 1번 도시 제외 나머지 도시 방문하고 1번 도시로 돌아가야하기 때문.
   
   
2. 위 코드 중 A & ~vj부분은 비트의 뺄셈 연산을 하는 부분이다.
   
   
3. 메모이제이션을 하지 않고 짠 코드는 시간초과가 났다.
   
   
4. if (map[i][j + 1] > minimum) continue;이 부분을 return으로 처리해서 계속 오답이 나왔었는데 return을 해버리면 뒤에 더 효율적인 경로를 무시해 버리기 때문에 continue로 작성하는데 맞다. 생각안하고 코드부터 쓰는 버릇의 최후
   
   
5. 내가 사용했던 테스트 케이스

느낀점

분명 3학년때 알고리즘 설계 과목 과제로 풀었었는데 다시 하려니까 헷갈렸다.

정답 ~.~