오늘 뭐했지

https://boj.ma/2001/t

그래프가 주어지고 보석이 위치한 노드가 주어집니다

그리고 간선마다 들고 지나갈수 있는 보석의 개수 제한이 있습니다.

1번 노드에서 출발해서 다시 1번 노드로 돌아오려고 할 때 가질수 있는 보석의 최대 갯수를 구하는 문제입니다.

완전탐색으로 먼저 접근해보면,

1번에서 출발하여 1번으로 돌아오는 모든 경로에 대해 확인하면 답을 구할 수 있지만

방문했던 노드를 또 방문 할 수 있기때문에 많은 경우의 수를 모두 확인해봐야 합니다.

방문했던 노드를 다시 방문가능하지만, 굳이 안봐도 되는 경우에 대해서는 거를 수 있지 않을까요?

문제의 예제의 그래프입니다.

1, 2, 3, 4, 5번 노드에 보석이 있고 가중치는 들고 지나갈 수 있는 보석의 개수입니다.

만약 모든 노드에서 보석을 줍지 않는다고 한다면, 영원히 그래프를 지나다닐 수 있을거에요.

그래서 어떤 노드에 대해서, 내가 1번 노드에서 보석을 주운 상태로 여기를 와본적이 있다면, 그 노드는 굳이 다시 안가봐도 된다는 거죠

마찬가지로, 1번 노드, 3번 노드, 5번 노드에서 보석을 주운 상태로 어떤 다른 노드로 가려고 하는데,

1, 3, 5번 노드에서 보석을 주운 상태로 다음 가려는 노드를 가본적이 있다면 안가봐도 되는 것입니다.

이제 그래프 탐색을 진행하면서 상태에 대해 잘 관리해주면 됩니다.

하지만 단순히 보석의 개수만으로 상태를 관리하면 올바르게 탐색이 안됩니다.

보석마다 번호를 매겨서 몇번째 보석을 갖고있는지까지 알고있어야 이미 보석을 주운 노드에 방문하더라도

또 보석을 줍는 일을 막을 수 있습니다.

${K <= 14}$ 이기 때문에 비트마스킹을 이용해 보석 보유 상태를 관리했습니다.

사실 문제 읽자마자 K <= 14 인거 보고 비트마스킹으로 풀어야겠다고 생각했습니다

그래서 visited[a][b] := a번 노드에 b상태로 와본적 있는지

라고 정의해서 bfs를 돌려주면 끝입니다.

#include <bits/stdc++.h>
#define endl "\n"
#define NM 202020
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//using ll = int64_t;
//using ull = uint64_t;
using namespace std;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };



int main() {
    fastio;
    
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> exist(n + 1, 0);
    for (int i = 1 ; i <= k; i++){
        int x;
        cin >> x;
        exist[x] = i;
    }
    
    vector<vector<pii>> graph(n + 1);
    
    // visited[a][b] := a섬에 b상태로 와봤는지
    vector<vector<int>> visited(n + 1, vector<int>(1 <<14, 0));
    
    for (int i = 0 ; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    
    // 이진수에서 1의 개수
    auto pop_count = [&](int x)->int{
        int ret = 0;
        while(x){
            if (x&1) ret++;
            x >>= 1;
        }
        return ret;
    };
    
    
    queue<pii> q;
    visited[1][0] = 1;
    q.push({1, 0});
    if (exist[1]){ // 1번 노드에 보석 존재하는 경우
        q.push({1, 1 << exist[1]});
        visited[1][1 << exist[1]] = 1;
    }
    
    while(!q.empty()){
        auto [cur, state] = q.front(); q.pop();
        int cnt = pop_count(state);
        for (auto [nxt, limit] : graph[cur]){
            // 못지나감
            if (cnt > limit) continue;
            
            // 그냥 가기
            if (!visited[nxt][state]){
                visited[nxt][state] = 1;
                q.push({nxt, state});
            }
            
            if (exist[nxt]){ // 다음 위치가 보석이 있는곳이고
                if (!(state & (1 << exist[nxt]))){ // 지금 안주운 상태
                    if (!visited[nxt][state | (1 << exist[nxt])]){ // 현재 상태에서 주워본적도 없음
                        visited[nxt][state | (1 << exist[nxt])] = 1;
                        q.push({nxt, state | (1 << exist[nxt])});
                    }
                }
            }
        }
    }
    
    int ans = 0;
    
    for (int i = 0 ;i < (1 << 14); i++){
        if (visited[1][i]){ // 1번에 i상태로 온적 있다.
            ans = max(ans, pop_count(i));
        }
    }
    cout << ans << endl;
    
    
    return 0;
}