[G1] 백준 2098번 외판원 순회 C++ 비트마스킹, 다이나믹 프로그래밍

리뷰

 

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

비트마스킹 + DP를 사용해 푸는 기본적인 외판원 순회 문제, 새로운 알고리즘을 알게 되었다.

 

 

전역 변수

• N : 배열 크기의 최대값을 정의할 상수 변수
• n : 도시의 수를 저장할 변수
• w : 인접 행렬을 저장할 배열
• dp : 다이나믹 프로그래밍 정보를 저장할 배열

 

함수

1. tsp

int tsp(int mask, int cur)

 

모든 도시를 순회하고 시작점으로 돌아오는 최소값을 구하는 함수

1. 매개 변수로 현재 도시 방문 비트 정보 mask와 마지막으로 방문한 도시 번호 cur을 전달 받는다.
2. 기저 조건으로 mask가 (1 << n) - 1 즉 모든 도시를 방문해 1비트가 n개인 경우 시작점으로 돌아가는 거리를 리턴한다.
3. 이 때 현재 도시에서 시작점으로 돌아갈 수 없는 경우 매우 큰 값을 리턴해 주어야 한다.
4. 두 번째 기저 조건으로 이미 dp값이 계산된 상태라면 dp에 저장된 값을 리턴해 준다.
5. 기저 조건에 해당하지 않는다면 현재 dp값을 매우 큰 값으로 초기화 해준다.
6. 0~n - 1번의 도시를 순회하며 만약 현재 도시에서 다음 도시로 이동이 불가하면 continue 처리해 준다.
7. 아직 방문하지 않았다면 현재 dp값과 거리 + tsp함수에 이동 후 정보의 값 중 작은 값으로 갱신해 준다.
8. 재귀 및 모든 탐색이 완료된 후엔 현재 dp값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, n * n의 인접 행렬을 초기화 해준다.
2. memset 메서드를 통해 dp의 초기값을 모두 -1로 변경해 준다.
3. tsp 함수에 초기 mask값 1과 현재 도시 번호 0번을 매개 변수로 전달하고 받은 리턴값을 출력해 준다.

 

트러블 슈팅

1. 도시들 사이에 길이 없을 수도 있는 경우를 체크해 주지 않아 Fail을 받았다.
2. 길이 없는 경우(가중치가 0이 주어진 경우) continue처리해 주었으나 58%에서 Fail을 받았다.
3. 모든 지역을 방문 후 다시 원점으로 돌아갈 때에도 현재 도시에서 원점으로 갈 수 있는지를 체크해 주어야 했다.
4. 첫 번째 기저 조건에서 길이 있다면 가중치를, 없다면 매우 큰 값을 리턴하여 AC를 받았다.

 

참고 사항

없음

 

 

정답 코드

#include<iostream>
#include<cstring>
using namespace std;

const int N = 16;
int n;
int w[N][N];
int dp[1 << N][N];

int tsp(int mask, int cur) {
	if (mask == (1 << n) - 1) {
		return !w[cur][0] ? 2e9 : w[cur][0];
	}
	if (dp[mask][cur] != -1) return dp[mask][cur];

	dp[mask][cur] = 2e9;
	for (int i = 0; i < n; ++i) {
		if (!w[cur][i]) continue;
		if (!(mask & (1 << i))) {
			dp[mask][cur] = min(dp[mask][cur], w[cur][i] + tsp(mask | (1 << i), i));
		}
	}
	return dp[mask][cur];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	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(1, 0);
}