[BOJ] #6497 전력난

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

---

난이도는 그렇게 높진 않았는데, 문제 자체에 함정이 몇 개 정도 있는 문제였던 것 같다. 질문 게시판에도 여럿 문제의 입력과 출력 조건에 대해 까다로워 하는 모습이 보였다. 다음은 질문게시판에 있는 한 글을 발췌한 것이다. 

 

https://www.acmicpc.net/board/view/145360

1. 제시된 예제는 테스트 케이스가 하나입니다만, 0 0이 등장하기 전에 테스트 케이스가 여러 개가 있을 수 있으므로, 각 테스트 케이스에 대한 정답을 차례차례 저장해두어야 합니다.

2. 모든 정답은 '0 0'이 입력된 이후에 순차적으로 출력해야 합니다. (댓글 보고 추가: 하나씩 출력하는 것도 가능하다면 이 항목은 무시하셔도 됩니다.)

=> 수정 : 필자가 직접 테스트 해 본 결과, 각 테스트 케이스 마다 하나씩 출력하여도 정답 판정이 되는 것 같다. 

3. 최소 필요 비용이 아니라, 최대 절약가능 비용을 출력해야 합니다.

 

MST를 구해서 해당 트리의 가중치의 합을 출력하면 되는 것이 아니라 절약한 비용의 최댓값을 구해야 하니, 모든 가중치에서 MST의 가중치의 합을 빼주어야 한다. 또한, 예제에서는 입력이 하나이지만, 실제로는 여러개의 입력이 계속 주어지고 마지막에 0 0 이 입력될 때 까지 계속 입력을 받아서 MST를 구성해야 하기 때문에 각 입력 케이스 마다 벡터나 배열같은 자료구조를 초기화 시켜주어야 한다. 필자 또한 이 함정들을 바로 캐치하지 못해서 몇번 오답을 제출했다.

다른 MST 문제들 처럼 프림 알고리즘과 크루스칼 알고리즘으로 둘 다 풀리는 문제이다. 필자 또한 두가지 다른 방법으로 풀어보았다.

#include <iostream>
#include <vector>
#include <queue>

#define MAX 200001

using namespace std;

int V,E;
vector<pair<int,int>> Graph[MAX];
bool visited[MAX] = { false };

vector<int> ans;

int prim() {
    priority_queue<pair<int,int>> pq;
    int total = 0;

    pq.push(make_pair(0,0));

    while (!pq.empty()) {
        while (!pq.empty() && visited[pq.top().second]) pq.pop();
        if (pq.empty()) break;

        int curr = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();

        visited[curr] = true;
        total += cost;

        for (int j=0; j<Graph[curr].size(); j++) {
            int next = Graph[curr][j].first;
            int newCost = Graph[curr][j].second;

            if (visited[next] == false)
                pq.push(make_pair(-newCost, next));
        }
    }

    return total;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    while (1) {
        cin >> V >> E;

        if (V==0 && E==0) break;

        int sum=0;
        for (int i=0; i<E; i++) {
            int x,y,z;
            cin >> x >> y >> z;

            Graph[x].push_back(make_pair(y,z));
            Graph[y].push_back(make_pair(x,z));

            sum += z;
        }

        ans.push_back(sum - prim());

        memset(visited, false, sizeof(visited));  // visited 배열 초기화
        for (int i=0; i<V; i++) Graph[i].clear();   // Graph 초기화
    }

    for (int a : ans) cout << a << '\n';

    return 0;
}

프림 알고리즘을 이용한 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 200001

using namespace std;

int V,E;

vector<pair<int,int>> Graph[MAX];
vector<pair<int, pair<int,int>>> Edge;
vector<int> parent;
vector<int> ans;

int getParent(int x) {
    if (x == parent[x]) return x;

    return getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);

    if (a<b) parent[b] = a;
    else parent[a] = b;
}

bool find(int a, int b) {
    return getParent(a) == getParent(b);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    while (1) {
        cin >> V >> E;

        if (V==0 && E==0) break;

        int sum = 0;
        for (int i=0; i<E; i++) {
            int x,y,z;
            cin >> x >> y >> z;

            Graph[x].push_back(make_pair(y,z));
            Graph[y].push_back(make_pair(x,z));

            sum += z;
        }

        for (int u=0; u<V; u++) {
            for (int j=0; j<Graph[u].size(); j++) {
                int v = Graph[u][j].first;
                int cost = Graph[u][j].second;

                if (u<v) Edge.push_back(make_pair(cost, make_pair(u,v)));
            }
        }

        sort(Edge.begin(), Edge.end());

        parent.resize(V);
        for (int i=0; i<V; i++)
            parent[i] = i;
        
        int total=0;
        for (int i=0; i<Edge.size(); i++) {
            int cost = Edge[i].first;
            int u = Edge[i].second.first;
            int v = Edge[i].second.second;

            if (!find(u,v)) {
                total += cost;

                unionParent(u,v);
            }
        }

        ans.push_back(sum - total);

        for (int i=0; i<V; i++) Graph[i].clear();
        Edge.clear();
        parent.clear();
    }

    for (int a : ans) cout << a << '\n';

    return 0;
}

크루스칼 알고리즘을 이용한 풀이

---

첫번째 정답이 프림, 두번째가 크루스칼에 해당한다. 이 문제에서 정점의 최대 개수가 200,000개로 좀 많기 때문에, 밀집 그래프에 해당한다고 판단하여 처음엔 프림으로 풀었으나, 크루스칼로 풀어본 케이스가 오히려 시간과 메모리는 더 적게 소요되었다. 왜지?

 

챗 GPT에 물어본 바, 정점의 숫자가 200,000개로 많기는 하지만, 간선의 숫자 또한 정점의 숫자와 크게 차이가 나지 않기 때문에 두 알고리즘의 성능의 차이가 크지 않았던 것 같다.