[백준(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;
}
PREVIOUS[Database] 여러 종류의 키