[백준] 2001 - 보석 줍기 힌트, 풀이 및 코드(C++)

https://www.acmicpc.net/problem/2001

2001번: 보석 줍기

! 본 게시글에서 설명하는 풀이는 (아마도?) 문제가 의도한 정해와 다른 방식으로 푼 풀이입니다.

 

1. 문제

- $N$ ($1 \leq N \leq 100$)개의 섬과 $M$ ($1 \leq M \leq 1,000$)개의 다리가 주어진다.

- 각 다리가 주어질 때, 각 다리가 버틸 수 있는 보석의 무게 제한 $c$($1 \leq c \leq 100$)이 함께 주어진다.

- 섬들 중, $K$ ($1 \leq K \leq 14$)개의 섬에는 보석이 있다.

- 시작 지점으로 가지고 돌아올 수 있는 최대 보석 개수를 구하여라.

 

 

2. 힌트

 

힌트 1

시작 섬에서 각 섬으로 갈 때, 최대한으로 들고갈 수 있는 보석의 개수는 어떻게 구할 수 있을까?

 

힌트 2

최소 스패닝 트리를 구하던 크루스칼/프림 알고리즘이나, 최소거리를 구하던 다익스트라 알고리즘을 살짝 응용하면 시작 섬과 다른 섬을 오갈 때 들고다닐 수 있는 보석의 최대 개수를 구할 수 있다.

이제 이 정보를 어떻게 써먹을 수 있을지 생각해보자.

 

힌트 3

어차피 시작 섬으로 돌아와야 하므로 보석을 아무리 많이 주워도 시작 섬과 연결된 보석 섬 사이의 최대 무게 제한까지만 보석을 가져올 수 있다.

 

 

3. 문제 관찰 과정 및 풀이

 

일단 문제를 처음 봤을 때, 뭔가 다른 그래프 문제에 비해서는 $N, M, K$의 크기 제한이 상당히 작게 설정되어 있다는 사실을 확인했다.

보통 이런 경우는 특정 풀이를 의도하고 낸 문제인 경우가 많지만, 처음에는 딱히 크기 제한에 신경쓰지 않고 풀이를 생각해 보았다.

 

우선 이 문제는 여타 그래프 문제와 다르게 각 다리가 가지는 무게 제한만 존재하며 섬과 다리를 여러 번 방문해도 되므로 각 섬에 도달 가능성 여부는 어떤 경로로 통해 가는지와 관계 없이 경로 상에 가장 무게 제한이 작은 다리와만 관계가 있다.

즉, 각 섬에 도달하는 최적의 경로는 시작 섬에서 해당 섬으로 가는 모든 경로들 중, 최소 무게 제한이 최대인 경로이다.

 

어차피 출발은 시작 섬에서만 하므로, 우선 시작 섬에서 보석이 있는 섬(이하 보석 섬이라고 통칭)들로 갈 때 들고다닐 수 있는 최대 보석 개수를 전부 구해보기로 했다.

시작 섬에서 다른 섬으로 갈 때 들고다닐 수 있는 최대 보석 개수는 최소 스패닝 트리나 다익스트라의 구현을 살짝 바꿔서, pq에 시작 노드에서 해당 노드로 가는 간선 가중치의 합을 저장하는 것이 아니라, $min($현재 노드로 올때까지의 최소 무게 제한$)$을 저장해 두면 쉽게 구할 수 있다.

 

 

여기서 핵심 아이디어는, "어차피 언젠가는 시작 섬으로 돌아와야 한다"는 것이다.

아무리 좋은 경로를 타고 많은 보석을 모았어도, 결국 그 보석들을 들고 시작 섬으로 돌아갈 수 있는 경로가 존재해야 한다는 것이다.

너무나도 당연한 소리같아 보이지만, 위 아이디어를 각각의 보석 섬에 적용시켜보면,

"어떤 보석 섬에 있는 보석을 줍기 위해선, 시작 점과 해당 보석 섬 사이 경로의 최대 무게 제한이 지금 가지고 있는 보석보다는 커야 한다"는 말과 동치이기 때문이다!

즉, 각 보석 섬에서 보석을 주울지 말지는 오로지 시작 섬과 해당 보석 섬 사이의 무게 제한에만 연관이 있다는 소리이다.

 

증명 겸 부연설명

보석 섬들을 각각 $G_1, G_2, G_3, \dots G_K$라 하고, 시작 섬을 $S$라 하고, 각 보석 섬에서 시작 섬 사이 최적의 경로의 무게 제한을 각각 $W_1, W_2, W_3, \dots W_K$라 하자.

어떤 보석 섬 $G_i$에서 $W_i$보다 많은 개수의 보석을 들고 시작 섬으로 돌아올 수 있다고 가정하자. (즉, 명제가 틀렸다고 가정하자.)

그렇다면 보석 섬 $G_i$에서 다른 어떤 섬 $I$ 사이의 최적 무게 제한과, 섬 $I$와 시작 섬 $S$ 사이의 최적 무게 제한이 모두 $W_i$보다 커야 한다.

그러나 그러한 섬 $I$가 존재한다면, $S$에서 $I$를 지나 $G_i$로 도달하는 경로가 최적 경로가 되므로, $W_i$가 보석 섬 $G_i$에서 시작 섬 사이의 최적 경로라는 가정에 모순된다.

 

따라서 모든 보석 섬에서 보석을 주워도 되는지의 여부는 시작 섬과 각 보석 섬 사이의 최적 경로의 무게 제한에만 연관이 있다. (귀류법)

 

 

여기까지 생각이 도달했으면 최대 보석 개수를 구하는 일은 매우 쉽다.

단순히 시작 섬과 각 보석 섬 사이의 무게 제한이 최소인 것부터 차례대로 그리디하게 보석을 가져올 수 있는지 판단하면 되기 때문이다.

여기서 주의할 점은, 시작 섬에 있는 보석은 어떤 무게 제한과도 상관 없이 반드시 주울 수 있으므로, 해당 경우에 대한 예외 처리를 해 주어야 한다는 것이다.

 

 

4. 코드

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, m, k;
    vector<vector<pair<int, int>>> v;
    int x;
    cin >> n >> m >> k;

    vector<int> gem(n+1, 0);
    for (int i=0; i<k; i++) {
        cin >> x;
        gem[x] = 1;
    }
    
    v = vector<vector<pair<int, int>>>(n+1);

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

    priority_queue<pair<int, int>> pq;
    vector<int> maxw(n+1, 0);
    for (int i=0; i<v[1].size(); i++)   pq.push({v[1][i].first, v[1][i].second});

    while (!pq.empty()) {
        int node = pq.top().second;
        int dist = pq.top().first;
        pq.pop();
        if (maxw[node])  continue;
        maxw[node] = dist;

        for (int i=0; i<v[node].size(); i++) {
            if (maxw[v[node][i].second])   continue;
            pq.push({min(dist, v[node][i].first), v[node][i].second});
        }
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> lpq;
    for (int i=1; i<=n; i++) {
        if (maxw[i]==0) continue;
        lpq.push({maxw[i], i});
    }

    int ans = 0;
    while (!lpq.empty()) {
        int dist = lpq.top().first;
        int node = lpq.top().second;
        lpq.pop();
        if (node == 1 || gem[node] == 0)  continue;
        if (dist <= ans)    continue;
        ans++;
    }
    if (gem[1]==1)  ans++;

    cout << ans;
}

5. 여담

사실 풀고 나서 "왜 이게 골드 1이지?" 에서 한 번 놀라고, "왜 이게 비트마스킹이지?" 에 두 번 놀랐다.

아마 K 범위가 수상하게 작게 주어져서 다들 비트마스킹으로 생각이 갔던 것 같은데, 차라리 K 범위가 아예 컸으면 난이도가 더 내려가지 않았을까?

 

가끔 문제를 보자마자 풀이가 떠오르는 문제들이 있는데, 이 문제가 바로 그런 문제였다.

힌트와 문제 풀이 부분이 다른 문제들에 비해 좀 빈약한 이유도, 어떤 대단한 생각들이나 시도를 하면서 얻어낸 결과가 아니라 그냥 "그래 보이는데 증명해볼까?" 하다가 나온 것이라...