[백준 2001번] [BFS / 비트마스킹] 보석 줍기

Approach

그래프 탐색 관련한 문제라는 것은 문제를 읽자마자 쉽게 파악할 수 있다.

문제 상황에서 가장 크리티컬한 지점은 탐색과정에서 보석을 얼마나 가지고 있는지를 기억해야한다는 것이다. 왜냐하면, 보석을 얼마나 가지고 있는지에 따라서 방문할 수 있는 지역이 달라지기 때문이다.

 

따라서 BFS를 돌리는 과정에서, 보석을 얼마나 가지고 있는지를 기억하고 있으면 된다. 같은 지역에 있는 보석은 1번만 주울 수 있으므로, 비트마스킹을 통해 1개의 정수로 어느 지역의 보석을 가지고 있는지를 쉽게 저장해놓을 수 있다.

 

추가적으로 같은 지역을 방문하더라도 보석이 달라지면 경향성이 달라지므로, visited를 2차원 배열로 잡는다.

위 문제와 비슷한 느낌으로 이해해주면 된다. https://viyoung.tistory.com/360

[백준 1194번] [BFS / 비트마스킹] 달이 차오른다, 가자.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;

bool visited[101][1 << 14];

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    int n, m, k;
    cin >> n >> m >> k;

    map<int, int> s;

    for(int i = 0; i < k; i++){
        int t;
        cin >> t;
        s[t] = i;
    }

    vector<vector<pii> > v(n + 1);

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }

    queue<pii> q;
    q.push(make_pair(1, 0));
    visited[1][0] = 1;

    int max_num = 0;

    while(!q.empty()){
        int cur = q.front().first;
        int key = q.front().second;
        q.pop();
        if(cur == 1){
            if (s.find(cur) != s.end()){
                max_num = max(max_num, __builtin_popcount(key | (1 << s[cur])));
            }
            else max_num = max(max_num, __builtin_popcount(key));
        }
        for (int i = 0; i < v[cur].size(); i++)
        {
            int to = v[cur][i].first;
            int limit = v[cur][i].second;
            if(s.find(cur) != s.end()){
                if(__builtin_popcount(key | (1 << s[cur])) <= limit && !visited[to][key | (1 << s[cur])]){
                    q.push(make_pair(to, key | (1 << s[cur])));
                    visited[to][key | (1 << s[cur])] = 1;
                }
            }
            if (__builtin_popcount(key) <= limit && !visited[to][key]){
                q.push(make_pair(to, key));
                visited[to][key] = 1;
            }
        }
    }

    cout << max_num << "\n";
    return 0;
}