← All Articles

[BAEKJOON] 2001. 보석 줍기

Posted on

문제 :

n(1 ≤ n ≤ 100)개의 섬이 m(1 ≤ m ≤ 1,000)개의 다리로 연결되어 있다. 각각의 다리는 서로 다른 두 섬을 연결하고 있으며, 서로 다른 두 섬은 최대 한 개의 다리로만 직접 연결되어 있다. 각각의 다리들의 튼튼한 정도는 서로 달라서, 각각의 다리마다 견딜 수 있는 무게의 제한이 다를 수 있다.

섬들 중, K(1 ≤ K ≤ 14)개의 서로 다른 섬에 각각 한 개씩 보석이 있다. 당신은 1번 섬에서 빈손으로 출발하여 최대한 많은 보석을 줍고 1번 섬으로 돌아오려 한다. 주의할 것은, 보석을 너무 많이 줍다 보면 다리를 건널 때 다리가 무게를 견디지 못하고 무너질 수 있다는 점이다. 따라서 당신은 다리가 무너지지 않는 한도 내에서 보석을 주워야 한다.

한 번 지난 적이 있는 다리와 섬을 여러 번 지날 수 있으며, 보석이 있는 섬을 지날 때에 그 보석을 줍지 않을 수도 있다고 하자.


입력 :

첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 b번 섬이 다리로 연결되어 있는데, 그 다리가 최대 c개의 보석만을 견딜 수 있다는 의미이다. 예를 들어 c가 2라면, 그 다리를 지날 때 보석을 0, 1, 2개 가지고 있어야 한다는 의미이다. 3개 이상의 보석을 가지고 그 다리를 지나려고 하면 다리가 무너진다.


출력 :

첫째 줄에 주울 수 있는 보석의 최대 개수를 출력한다.



풀이 :

우선 일반 탐색보다 더 어렵게 느껴졌던 이유는 방문했거나 지나친 섬과 다리를 다시 재 방문할 수 있었고 보석을 줍지 않을 수도 있다는 점이었던 것 같다.

본 문제는 비트마스킹을 떠올리고 효과적으로 사용할 줄 안다면 쉽게 접근할 수 있는 문제인 듯 했다.

우선 방문했던 섬들을 재 방문할 수 있기 때문에 일반적인 DFS와 BFS 방식은 사용할 수 없을 것이라고 예상했다.

따라서 해당 섬에 도착했을 때 주운 보석들을 비트마스크로 표현해 visit 배열을 만든다면 중복 방문을 없앨 수 있을 것이라 생각했다.

또 이 방법으로 문제를 해결할 수 있을 것이라고 생각했던 큰 이유 중 하나는 섬의 갯수는 100개 이하이지만 그 중 보석을 가지고 있는 갯수는 14개 이하에 불과했기 때문에 비트마스크로 표현하기 충분하다고 느꼈다.



코드 :

코드 보기/접기 
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>

#define pii pair<int, int>

using namespace std;
typedef struct Node {
    int idx, cnt, cntval;
};
bool visit[101][1 << 15];
vector<vector<pii>> adj;
vector<int> jewelry;
int n;

int bfs() {
    int answer = 0;
    queue<Node> q;
    q.push(Node{1, 0, 0});
    visit[1][0] = true;

    while (!q.empty()) {
        int curidx = q.front().idx, curcnt = q.front().cnt, curcntval = q.front().cntval;
        q.pop();
        if (curidx == 1) answer = max(answer, curcnt);

        int size = adj[curidx].size();
        for (int k = 0; k < size; k++) {
            int cmpidx = adj[curidx][k].first, cmpweight = adj[curidx][k].second;
            if (cmpweight < curcnt) continue;
            if (!visit[cmpidx][curcntval]) {
                visit[cmpidx][curcntval] = true;
                q.push(Node{cmpidx, curcnt, curcntval});
            }
            if (jewelry[cmpidx] != -1) {
                int cmpcntval = curcntval | (1 << jewelry[cmpidx]);
                if (visit[cmpidx][cmpcntval]) continue;
                visit[cmpidx][cmpcntval] = true;
                q.push(Node{cmpidx, curcnt + 1, cmpcntval});
            }
        }
    }

    return answer;
}

int main() {
    int m, k, input, i, fir, sec, val;
    cin >> n >> m >> k;

    jewelry.resize(n + 1, -1);
    adj.resize(n + 1);

    for (i = 1; i <= k; i++) {
        cin >> input;
        jewelry[input] = i;
    }

    while (m--) {
        cin >> fir >> sec >> val;
        adj[fir].emplace_back(sec, val);
        adj[sec].emplace_back(fir, val);
    }

    cout << bfs() << '\n';

    return 0;
}


AlgorithmalgorithmbaekjoonC++