보석 줍기

백준 2001번: 보석 줍기

아이디어

현재 가지고 있는 보석의 상태를 비트로 표현한다. 섬에 방문할 때 이전에 같은 보석 상태로 방문한 적이 없으면 방문한다. 1번 섬으로 돌아왔을 때 현재 가지고 있는 보석 개수를 가지고 최댓값을 갱신한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, M, K, MAX = 0;
int jew[101];
bool visited[101][1<<15];
vector<vector<pair<int, int>>> v(101);

void solve(int pos, int j) {
    visited[pos][j] = true;
    int jcnt = __builtin_popcount(j);
    if (pos == 1) {
        if (jew[1] && !(j&(1<<jew[1]))) jcnt++;
        MAX = max(MAX, jcnt);
    }
    
    for (auto p : v[pos]) {
        int next = p.first;
        int limit = p.second;
        if (!visited[next][j] && limit >= jcnt) {
            solve(next, j);
        }
        if (jew[pos] && !(j&(1<<jew[pos]))) {
            if (!visited[next][j|(1<<jew[pos])] && limit >= jcnt+1) {
                solve(next, j|(1<<jew[pos]));
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        jew[x] = i+1;    
    }
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    solve(1, 0);
    cout << MAX;
    return 0;
}

여담

1번 섬에 마지막으로 도착해서 보석을 줍는 경우를 생각하지 못했다.
__builtin_popcount(x) 라는 내장 함수로 1의 개수를 셀 수 있다. 그냥 2로 나누면서 세도 되는데 저게 훨씬 빠르다. 사실 그냥 count 1씩 올리면서 함수 인자로 넘기면 되는데 그냥 멋있어서 써봤다.
!(j&(1<<jew[pos])) 처럼 괄호 여러개를 사용한 이유는 비트 연산자의 우선순위가 낮기 때문이다. 그냥 앞에 ! 달아버리면 not j와 and 연산을 수행한다. 조심하도록 하자.