[BOJ] 외판원 순회(2098)

[백준(BOJ)] 외판원 순회(2098) C++

문제 : BOJ_2098번 외판원 순회

문제 설명

비트마스킹

n 개의 여행지가 있을 때, 각 여행지에서 다른 여행지로 갈 수 있는 비용이 주어집니다.
이때 비용을 최소한으로 해서 출발한 여행지에서 모든 여행지를 방문한 뒤 다시 출발한 여행지로 돌아오는 비용을 구하는 문제입니다.
이때 한 번 방문했던 여행지는 다시 방문할 수 없습니다.
비트 마스킹 외에도 여러 가지 방법으로 해결할 수 있는 유명한 문제입니다.
여행지의 수가 최대 16이기 때문에 16개의 자리수를 만들고 비트 연산으로 방문한 여행지를 체크하는 방식으로 비트 마스킹으로 해결할 수 있습니다.

Solution

recursion 함수를 만들어 줍니다.
이때, 함수의 내용은 recursion(현재 도시, 방문한 도시들)입니다. 이때 함수의 두 번째 인자인 방문한 도시들에 대해선 배열을 할당하는 것이 아닌 16자리의 비트 연산자로 방문한 도시의 정보를 전달해 주어야 합니다.
현재 도시에서 for 문을 순회하여 갈 수 있는 여행지로 다시 재귀로 들어가고, 비트 마스킹으로 모든 도시에 방문했음을 확인한 뒤, 그 현재 도시에서 처음 도시로 이동할 수 있다면 모든 비용을 return 해 줍니다.
각각의 도시를 방문할 때의 비용을 현재 비용에서 + 해주며 재귀를 하고, 이 쌓인 값들을 항상 min 함수로 최솟값을 구하도록 하여 최종 값이 최소가 나오게 해야 합니다.

Description

• vis == (1 << N) - 1) 첫 번째 방문한 도시를 0번째로 지정했기 때문에 해당 조건이 모든 도시를 방문한 조건입니다.
• vis & (1 << i) “&”를 활용해 현재 조건이 i 번 째 도시를 방문한 상태인지 확인할 수 있습니다.
• memset(dp, -1, sizeof(dp)) dp 메모제이션을 위해서 모든 dp 값을 -1로 초기화해줍니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 9999999999
using namespace std;
int N;
int map[16][16];
int dp[16][1 << 16];
int recursion(int now, int vis) {
	int &ret = dp[now][vis];
	if (ret != -1) return ret;
	if (vis == (1 << N) - 1) {
		if (map[now][0] != 0) return map[now][0];
		else return INF;
	}
	ret = INF;
	for (int i = 0; i < N; i++) {
		if (vis & (1 << i) || map[now][i]==0) continue;
		ret = min(ret, recursion(i, vis | (1 << i)) + map[now][i]);
	}
	return ret;
}
int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << recursion(0, 1) << '\n';
	return 0;
}