백준 2098번 외판원 순회

< 백준 2098번 외판원 순회 - 마포 코딩박 >

사용한 알고리즘: 비트 마스킹, DP


 외판원 순회문제는 매우 유명한 비트마스킹 문제입니다. 한 도시에서 출발하여 모든 도시를 들러서 다시 처음 도시로 올 것이므로 어떤 도시에서 출발하든 순회 비용이 같습니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~8)
 'dp[k][visited] : k: 현재 도시, visited: 방문했던 도시들 상태에서 순회를 마치는데 드는 최소비용' 이라고 설정하였습니다.
 방문도시(visited)는 2진법 형태로 저장합니다.
 예를 들어 1번도시, 3번도시, 16번도시를 방문한 상태는 1000000000000101 로 저장되어 있습니다.

(2) (코드 10~30)
 dp값을 계산해 줍니다. 어떤 도시에서 출발하든 순회비용은 변함없으므로 1번도시(index=0) 에서 출발했습니다.
 현재 도시와 연결된 방문하지 않은 모든 도시를 재귀적으로 방문합니다.
 모든 도시를 방문하고 다시 출발도시 (1번도시) 로 돌아오는 경우를 기저값입니다.
 i도시 방문 여부는 저장해놓은 visited | (1<<i) 로 or 연산으로 합니다.
 모든 도시 방문여부는 visited == (1<<N)-1 로 합니다. 참고로 (1<<N)-1 = 111...1 (1이 N개) 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 비트마스킹 + DP
	const int IMPOSSIBLE = 1987654321;
	int N, W[16][16];
	// dp[k][state] : k번째 마을, state: 방문했던 도시들을 2진법으로 표시.
	int dp[16][1<<16];
	int TSP(int current, int visited){
	int &ret = dp[current][visited];
	if(ret != -1)
	return ret;
	// 모든 마을 방문했는가
	if(visited == (1<<N)-1){
	// current -> 0 이동 가능한지
	if(W[current][0] != 0)
	return W[current][0];
	// 가능하지 않으면
	return IMPOSSIBLE;
	}
	ret = IMPOSSIBLE;
	for (int i = 0; i < N; ++i){
	// 방문했거나 || current -> i 로 길이 없거나
	if(visited & (1<<i) || W[current][i] == 0)
	continue;
	ret = min(ret, TSP(i, visited|(1<<i)) + W[current][i]);
	}
	return ret;
	}
	int main (){ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j)
	cin >> W[i][j];
	}
	memset(dp,-1,sizeof(dp));
	cout << TSP(0,1) << '\n';
	return 0;
	}

view raw BOJ 2098.cpp hosted with ❤ by GitHub