https://www.acmicpc.net/problem/2098
[필자사고]
이 문제는 비트 마스킹을 이용하여 메모리제이션을 효율적으로 가져가 푸는 문제이다.
필자는 비트마스킹 개념이 약한 편이라 이 문제를 풀지 못하였고 낮은 단계부터 천천히 풀어봐야 될거 같다.
문제를 보면서 DFS를 이용하여 해당 방문한곳을 체크해가며 최소값으로 cost 비용을 갱신하는 형태로 코드를 짰다.
[코드 해설]
- 입력 처리 및 초기화 (Input 함수)
- 사용자로부터 입력받은 값으로 N개의 노드와 그 간선의 비용을 저장한다.
- 2차원 벡터 arr는 간선의 비용을 저장하며, 초기 크기를 N x N으로 설정한다.
- 2차원 벡터 cost는 각 노드와 방문 상태(bit)를 조합한 경우의 최소 비용을 저장하기 위해 사용되며, 초기값은 -1로 설정된다.
- 모든 노드의 비용을 입력받아 arr에 저장하고, 최종적으로 모든 노드를 방문했음을 나타내는 answerBit는 (1 << N) - 1로 설정한다.
- 깊이 우선 탐색 (DFS 함수)
- 현재 노드와 방문 상태를 기반으로 최소 비용을 계산한다.
- 종료 조건: 모든 노드를 방문했을 경우(curBit == answerBit), 시작 노드로 돌아가는 비용을 반환한다. 만약 해당 간선이 없으면 INF를 반환한다.
- 메모이제이션: cost[curNode][curBit] 값이 이미 계산된 경우 해당 값을 반환하여 중복 연산을 방지한다.
- 최소 비용 갱신: 현재 노드에서 이동 가능한 다른 노드에 대해, 간선 비용과 DFS 결과를 더한 값을 비교하며 최소값을 업데이트한다.
- 게임 시작 (Game_Start 함수)
- DFS 탐색을 시작하며, 초기 노드는 0번 노드이고 방문 상태는 1번 비트(1)로 설정된다.
- 최종적으로 계산된 최소 비용을 출력한다.
- 메인 함수 (main 함수)
- Input 함수로 데이터를 입력받고 초기화를 수행한다.
- Game_Start 함수를 호출하여 전체 과정을 시작한다.
- 결과적으로, 모든 노드를 방문한 뒤 시작 노드로 돌아오는 최소 비용을 출력한다.
[소스 코드]
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 16
#define INF 987654321
using namespace std;
vector<vector<int>> arr;
vector<vector<int>> cost;
int N;
int answerBit;
void Input() {
cin >> N;
arr.resize(N);
cost.resize(N);
for (int i = 0; i < N; i++) {
cost[i].resize(1 << N,-1);
arr[i].resize(N);
}
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
cin >> arr[i][k];
}
}
answerBit = (1 << N) - 1;
}
int DFS(int curNode,int curBit) {
if (curBit == answerBit) {
if (arr[curNode][0] == 0) return INF;
else return arr[curNode][0];
}
if (cost[curNode][curBit] != -1) return cost[curNode][curBit];
cost[curNode][curBit] = INF;
for (int i = 0; i < N; i++) {
if (arr[curNode][i] == 0)continue;
if ((curBit & (1 << i)) == (1 << i))continue;
cost[curNode][curBit] = min(cost[curNode][curBit], arr[curNode][i] + DFS(i, curBit | 1<<i));
}
return cost[curNode][curBit];
}
void Game_Start() {
cout << DFS(0, 1) << '\n';
}
int main(void) {
Input();
Game_Start();
}