cdjs의 코딩 공부방

https://acmicpc.net/problem/1185

1. 문제

- $N$개의 나라에 방문하는 비용과, $P$개의 도로들의 통행 비용이 주어진다.

- $N$개의 나라를 모두 연결하도록 $N-1$개의 도로만을 남긴 상태로, 나라에 방문하는 비용과 도로들을 이용하는 비용의 최솟값을 구하여라.

- 이때, 여행을 시작하는 나라는 아무렇게나 정할 수 있으나 끝내는 나라는 반드시 시작하는 나라여야만 한다. (즉, 시작 나라로 돌아와야 한다.)

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정

문제를 처음 보자마자 이런 생각이 들었다.

"$N$이 $10,000$까지인데 시작 나라도 정해주지 않았으면서, $N-1$개의 도로만을 남기라고? 시간 안에 되나?"

만약 시작 나라를 하나씩 정하면서 각각의 최소 비용을 구하는 방식으로 문제를 해결하고자 하면, 최소 비용을 구하는 시간복잡도가 많아봤자 $O(logN)$ 수준이어야 하는데, 도로 개수가 $N-1$개이므로 모든 도로를 돌아보지도 않으면서 최소 비용을 $O(logN)$ 안에 구하는 것은 불가능해 보인다.

따라서, 뭔가 문제 속에 숨겨진 관찰을 통해 문제를 해결해야 한다는 뜻이다.

일단 가장 처음 한 가정은 "그냥 비용이 작은 도로만 고르면 안되나?" 였다.

물론 당연히 틀린 가정이라고 생각했지만, 이런 틀린 가정을 부수는 반례를 생각해보며 문제의 관찰을 더욱 다채롭게 할 수 있다고 생각해 반례를 생각해 보았다.

위 반례는 단순하게, "방문 비용이 높은 나라를 여러 번 방문할 수 밖에 없이 도로를 연결하는 경우"였다. 그런데 그렇다면 "방문 비용이 높은 나라를 여러 번 방문할 수 밖에 없는"경우는 과연 어떤 경우일까?

사실 딱 여기까지만 생각하고 머리가 어질어질해지는 바람에 일단 메모장에 적어만 두고 간단한 예시들을 작성해 보았다.

가장 단순한 예시는 나라가 오로지 두 개 이고 사이클이 생기는 도로가 생겼을 경우였는데, 이 경우에는 자명히 도로의 비용만을 고려하면 최고의 답안이 나오므로 무시하고 다음으로 넘어갔다.

다음 예시는 나라가 세 개이고 사이클이 생기는 도로가 있을 경우였는데, 이 경우에는 도로를 단 하나만 없애야 총 2개의 도로로 모든 나라를 연결할 수 있었다.

각 정점을 1, 2, 3이라고 했을 때, 간선을 잘랐을 때 다음과 같은 경우만 나온다.

1-2-3 (2가 중앙에 있는 경우),  1-3-2 (3이 중앙에 있는 경우), 2-1-3(1이 중앙에 있는 경우)

일단 단순하게 생각하기 위해 첫 번째 1-2-3인 경우만 보고 생각해 보았다.

시작 나라가 1번 나라인 경우, 1-2 간선은 2회, 2-3간선은 2회 타고, 1번 나라는 2회, 2번 나라는 2회, 3번 나라는 1회 방문하게 된다.

시작 나라가 2번 나라인 경우, 1-2 간선은 2회, 2-3간선은 2회 타고, 1번 나라는 1회, 2번 나라는 3회, 3번 나라는 1회 방문하게 된다.

시작 나라가 3번 나라인 경우, 1-2 간선은 2회, 2-3간선은 2회 타고, 1번 나라는 1회, 2번 나라는 2회, 3번 나라는 2회 방문하게 된다.

뭔가 이렇게 나열하고 보니 특이한 점을 찾을 수 있었다.

우선, 모든 도로는 시작 나라를 어떻게 잡는지와 관계 없이 오로지 두 번씩만 타고 있었고, 나라 방문 횟수는 시작하는 나라는 한 번 더 방문하며, 중앙에 있는 나라는 다른 나라보다 조금 더 방문하는 것 같아 보였다.

이 과정 속에서, "혹시 모든 도로는 무조건 두 번씩 이용해야 하나?"와, "나라를 많이 방문하게 되는 경우가 다른 나라 사이에 껴 있는 경우인건가?" 라는 생각을 하게 되었다.

4. 풀이

우선 나라가 $N$개이고, 도로가 최적으로 $N-1$개로 선택되어 있으며 시작 나라도 이미 최적으로 결정되었다고 가정하자.

즉, 이미 모든 것이 정해진 상태에서 그냥 모든 도시를 방문하는 최소 비용만 계산해 보자는 뜻이다.

우선 도로를 이용하는 데 필요한 비용을 간단하게 계산해 보자.

도로가 $N-1$개 뿐이므로, 관찰을 통해 다음과 같은 성질들을 확인할 수 있다.

    - 모든 도로를 전부 다 최소한 한 번씩은 사용해야만 한다. (각 나라를 연결하는 경로가 유일하기 때문)

    - 시작 나라를 $S$라 했을 때, 모든 나라를 순회하고 $S$로 돌아오려면 반드시 다른 모든 나라에 들어갔다 나오는 동작을 해야만 한다. 따라서, 모든 도로는 최소한 두 번씩은 사용해야만 한다.

    - 어떤 나라를 방문하기 위해 도로를 사용한 뒤 다시 돌아오기 위해 그 도로를 사용하여 총 2회 사용했다면, 더 이상은 그 도로를 사용할 필요가 없다. 더 이상 그 도로를 사용해서 방문해야 하는 나라가 없어지기 때문이다.

따라서, 시작 나라가 어디에 있든지간에 모든 도로는 반드시 단 두 번만 사용하게 된다.

그렇다면 나라를 방문하는 데 필요한 비용은 어떻게 계산할 수 있을까?

만약 시작 나라 $S$에서 나라$A$로 연결하는 도로 하나와, 나라$A$에서 나라 $B, C, D$로 이동할 수 있는 도로가 하나씩 존재한다면, (즉 $(S, A), (A, B), (A, C), (A, D)$를 연결하는 도로가 존재한다면) 필연적으로 각 도로를 최소 한 번씩은 사용해야만 한다.

그렇기 때문에 나라 $A$에서 나라$B$로 이동한 뒤에 다시 나라 $C, D$로 이동하기 위해선 반드시 나라 $A$를 재방문해야 하고, 나라 $A$에서 나라 $C$로 이동한 뒤에 다시 나라 $D$로 이동하기 위해선 다시 반드시 나라 $A$를 재방문해야 한다.

또한, 다시 시작 나라$S$로 돌아가야 하므로 나라 $D$를 방문한 뒤에 다시 나라 $A$로 돌아가서 나라 $S$로 돌아가야만 한다.

이 때, $A$를 방문하는 횟수는, 시작 나라 $S$에서 $A$로, $B$에서 $A$로, $C$에서 $A$로, $D$에서 $A$로 방문하는 총 4회이다.

그리고, 이렇게 방문하는 횟수는 나라 $A$에 연결되어 있는 도로의 개수와 동일하다는 점을 확인할 수 있다.

실제로 나라 $B, C, D$ 모두 연결된 간선 개수(1개) 만큼만 방문한다는 사실을 알 수 있다.

주의할 점은 시작 나라 $S$인데, 시작 나라 $S$는 초기에 방문하는 비용도 계산해야 하므로 연결된 간선 횟수보다 한 번 더 방문해야 한다는 것이다.

... 사실 말은 길게 했지만, 쓰고 보니 그냥 트리에서의 DFS를 돌리는 것을 생각하면 쉬울 것 같다.

나라가 $N$개이고 도로가 $N-1$개이므로, 이러한 그래프는 시작 나라를 루트 노드로 둔 트리라고 생각해도 좋다. (사이클이 존재하지 않으므로)

그리고 루트 노드에서부터 모든 노드를 순회한 뒤에 다시 루트 노드로 돌아오기 위해선, 반드시 DFS로 가장 깊이 있는 노드까지 들어간 뒤에 빠져나오며 순회하는 방법밖에는 없다.

이 경우, 당연히 모든 간선들을 2회 방문하고, 루트 노드를 제외하면 모든 노드는 연결된 간선의 수만큼 방문해야 하는 것이다.

따라서, 이 과정을 통해 우리는 다음과 같은 사실을 도출해 냈다.

"이미 그래프가 만들어진 경우, 해당 그래프에서 시작 나라에서 시작하여 모든 나라를 순회하고 시작 나라로 돌아오는 데 필요한 비용은 (모든 도로의 비용 * 2) + (각 나라의 비용 * 나라와 연결된 도로 개수) + (시작 나라의 비용) 으로 나타낼 수 있다!"

그럼 이를 토대로, 다음과 같은 사실도 깨달을 수 있다.

"어차피 시작 나라는 총 비용에서 (시작 나라의 비용) 만큼만을 차지하므로, 시작 나라는 단순히 비용이 최소인 나라를 아무렇게나 잡아도 된다!"

그런데 그럼 어떻게 $P$개의 도로에서 $N-1$개의 도로만을 남기면서 저렇게 그래프를 형성할 수 있을까?

위에서 필요한 비용식인,

(모든 도로의 비용 * 2) + (각 나라의 비용 * 나라와 연결된 도로 개수) + (시작 나라의 비용)

을 다시 생각해 보자.

(시작 나라의 비용) 부분은 어차피 그래프를 어떻게 잡는지와 관계 없이 (방문 비용이 최소인 나라의 비용)으로 두면 된다는 사실을 깨달았으니, 이는 그래프 연결과는 연관이 없는 부분이므로 무시하자.

또한, (모든 도로의 비용 * 2) + (각 나라의 비용 * 나라와 연결된 도로 개수)를 도로 연결 관점에서 보자면, 도로 하나를 연결할 때 드는 비용은 (해당 도로의 이동비용 * 2) + (해당 도로가 연결하는 각 나라의 비용의 합) 으로 나타낼 수 있다.

따라서, 그래프를 형성할 때는 (도로의 이동비용 * 2) + (해당 도로가 연결하는 각 나라의 비용의 합) 을 최소화 하는 방식으로 $N-1$개의 도로를 고르기만 하면 된다!

이는 간선 하나의 비용이 (해당 간선의 비용 * 2) + (해당 간선이 연결하는 각 정점의 비용의 합)인 최소 스패닝 트리를 만드는 것과 완벽하게 동일하므로, 풀이는 단순히 위의 식대로 간선의 비용을 설정해준 뒤 최소 스패닝 트리를 만들어 준 다음, 비용을 계산해 주면 된다.

5. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, p;
    int a, b, c;
    int cost[10005];
    int minn, st;
    int ans = 0;
    vector<int> vst;
    vector<vector<pair<int, int>>> edge;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    cin >> n >> p;
    edge = vector<vector<pair<int, int>>>(p+1);
    vst = vector<int>(n+1, 0);

    minn = INT_MAX;
    st = -1;
    for (int i=1; i<=n; i++) {
        cin >> cost[i];
        if (minn > cost[i]) {
            st = i;
            minn = cost[i];
        }
    }
    ans += minn;

    for (int i=0; i<p; i++) {
        cin >> a >> b >> c;
        edge[a].push_back({cost[a]+cost[b]+2*c, b});
        edge[b].push_back({cost[a]+cost[b]+2*c, a});
    }

    for (int i=0; i<edge[st].size(); i++) {
        pq.push({edge[st][i].first, edge[st][i].second});
    }
    vst[st] = 1;

    while (!pq.empty()) {
        int node, dist;
        node = pq.top().second;
        dist = pq.top().first;
        pq.pop();

        if (vst[node])  continue;
        vst[node] = 1;
        ans += dist;

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

    cout << ans;

}

6. 여담

문제 작성하다가 본 건데, 문제 처음에는 나라라고 하다가 중간엔 갑자기 "모든 도시를 한 번 이상 방문한다"고 한다...?

사실 필자도 풀이 작성하면서 자꾸 나라를 도시라고 잘못 써서 지웠다 다시 쓰는 경우가 수도 없이 많았다...