[DFS] BOJ 2001 보석 줍기

문제 링크 : www.acmicpc.net/problem/2001

2001번: 보석 줍기

보석의 개수가 최대 14개이므로, 어떤 보석을 주운 상태인지 비트마스크를 통해 나타낼 수 있음을 캐치하자.

보석이 있는 섬에 도착했을 때, 보석을 주운 후 다음 섬으로 이동할 수도 있고 줍지 않고 이동할 수 있다.

색칠된 정점이 곧 보석이 있는 섬이다.

위와 같은 예제 그래프에서, 1번 노드에서 출발해 최대로 보석을 주웠을 때의 개수는 4이다.

경로는 다음과 같다.

① 1번 섬에서 보석을 줍지 않고 5번 섬으로 이동해 보석을 줍는다.

② 1번 섬으로 돌아와 3번 섬으로 가서 보석을 줍는다. (1번 섬에서는 여전히 줍지 않음)

③ 2번 섬으로 가 보석을 주운 뒤, 마지막으로 1번 섬으로 돌아와 보석을 줍는다.

 

핵심은, 각 보석을 주운 상태를 비트마스크로 나타낸 수를 State라 할 때 같은 State로 동일한 점은 방문할 필요가 없다는 것이다.

이 점을 이용해 제시된 섬의 그래프를 비트마스크만큼 확장한 후, DFS를 통해 가능한 모든 경우를 체크한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n, m, k, answer;
vector<p> adj[101];
bool visit[1 << 16][101];        //도달 가능한지만 확인(0, 1)
int gem[101];
 
void get_dp(int state, int cur, int cnt) {
    visit[state][cur] = true;
    if (cur == 1) answer = max(answer, cnt);
 
    //이동 가능한 섬들을 모두 확인
    for (int i = 0; i < adj[cur].size(); i++) {
        int nextnode = adj[cur][i].first;
        int weight = adj[cur][i].second;
 
        if(!visit[state][nextnode] && weight >= cnt)
            get_dp(state, nextnode, cnt);
 
        //만약 현재 섬에 보석이 있다면, 줍는 경우와 줍지 않는 경우 모두 확인
        if (gem[cur] != -1) {
            if (state & (1 << gem[cur])) continue;
            int nextstate = state | (1 << gem[cur]);
            int next_gem = cnt + 1;
 
            if (!visit[nextstate][nextnode] && weight >= next_gem)
                get_dp(nextstate, nextnode, next_gem);
        }
    }
}
 
void init() {
    int f, s, w;
    cin >> n >> m >> k;
 
    memset(gem, -1, sizeof(gem));
    for (int i = 0; i < k; i++) {
        cin >> f;
        gem[f] = i;
    }
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s >> w;
        adj[f].push_back({ s, w });
        adj[s].push_back({ f, w });
    }
 
    memset(visit, 0, sizeof(visit));
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    adj[1].push_back({ 1, 100 });
    get_dp(0, 1, 0);
 
    printf("%d\n", answer);
 
    //system("PAUSE");
    return 0;
}
 

 

※ 그래프를 인접 리스트로 나타낼 때, 마지막에 (1, 1, 100) 간선을 추가하는 이유는 1번 정점에서 보석을 주운 후 탐색을 마치는 경우에 대한 안전장치로 이해하면 된다.