[백준/C++] 전력난 (No. 6497)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 모든 집에서 다른 집으로 이동하기 위해서는 길에 가로등이 켜져있어야 하며, 다른 집을 거쳐서 이동할 수 있다.

 

이때, 가로등을 최소로 켜두면 얼마만큼의 비용을 절약할 수 있는지 계산하는 문제다.

 

즉, 모든 집들이 연결되어 있을 경우의 최소 비용을 구해 총 비용에서 빼면 절약한 비용이 나오므로, MST 문제임을 알 수 있다.

 

제한 사항을 보면 m과 n이 200,000이므로 prim 알고리즘이나 크루스칼 알고리즘을 이용해 문제를 풀면 된다.

 

나는 모든 간선을 우선순위 큐에 넣어서 최소 비용을 구하는 방법으로 문제를 해결했다.

 

간선의 비용이 주어지므로 간선의 비용이 입력될 때 마다 priority_queue에 넣었다.

 

이후 Union-Find를 이용해 같은 집합에 속해있는지 판단하고 만약 다른 집합에 속해있다면, 두 집합을 합치도록 구현했다.

 

모든 간선을 비교했다면, 만들어진 MST가 가로등을 키는데 드는 가장 적은 비용이므로 모든 가로등을 켰을 경우의 비용에서 빼 얼마나 절약됐는지 출력했다.

 

 

​

[아이디어 정리]

1. 간선이 주어지면 priority_queue에 두 집과 비용의 정보를 저장한 값을 넣는다.
2. 이후 priority_queue에서 비용이 가장 작은(길이 가장 짧은) 가로등을 꺼내고 두 집이 같은 집합에 속해있다면 pass하고, 만약 다른 집합에 속해있다면 가로등의 비용을 더한 다음 두 집합을 하나의 집합으로 합친다.
3. 최종적으로 계산된 MST의 비용을 모든 가로등의 비용에서 뺀 값을 출력한다. 

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

struct lig {
    int st;
    int ed;
    int cost;
};

struct cmp {
    bool operator ()(const lig &a, const lig &b)const {
        return a.cost > b.cost;
    }
};

int FindPar(vector<int> &par, int a) {
    if (par[a] == a) {
        return a;
    }
    return par[a] = FindPar(par, par[a]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N,M;
    while (true) {
        cin >> N >> M;
        if (N == 0 && M == 0) {
            break;
        }
        int st, ed, cost;
        lig LIG;
        priority_queue<lig, vector<lig>, cmp> q;
        int answer = 0;
        for (int i = 0; i < M; i++) {
            cin >>LIG.st >> LIG.ed >> LIG.cost;
            q.push(LIG);
            answer += LIG.cost;
        }
        vector<int> par(N);
        for (int i = 0; i < N; i++)
            par[i] = i;

        int a, b;
        while (!q.empty()) {
            LIG = q.top();
            q.pop();
            a = FindPar(par, LIG.st), b = FindPar(par, LIG.ed);
            if (a!=b){
                par[a] = b;
                answer -= LIG.cost;
            }
            else {
            }
        }
        cout << answer<<"\n";
    }
    
    return 0;
}

 

---

단계별로 풀기에 문제가 분류되어 있어서 쉽게 푼 것 같다...

얼른 일정 단계까지 알고리즘을 풀고 골랜디를 해야겠다.

어떤 점이 부족한지 파악을 한번 해봐야 할 것 같은데;;