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

백준의 전력난(6497) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

- 주어진 집 사이사이에 있는 거리에 불을 켜야 하는데, 가장 비용을 절약하면서 모든 거리에 불을 비출 수 있도록

  불을 켜야 할 때, 얼마를 절약할 수 있는지 구해야 하는 문제이다.

  본인은 이 문제를 '최소스패닝트리(Minimal Spanning Tree)' 를 구현하는 방식으로 접근해 보았다.

  왜냐하면, "주어진 간선에 대한 정보들을 통해서, 최소의 비용으로 모든 정점을 연결" 하는 최소스패닝트리와,

  "주어진 거리에 대한 정보들을 통해서, 최소의 비용으로 모든 집으로 가는 거리에 불을 켜야 하는 것" 이

  동일한 특성을 갖기 때문이다.

  최소스패닝트리는 일반적으로 구현할 때 사용하는 알고리즘이 '크루스칼 알고리즘'과 '프림 알고리즘' 2가지가 있다.

  설명을 보기에 앞서, 크루스칼과 프림 알고리즘에 대해서 잘 모른다면 아래의 글을 먼저 읽고 오도록 하자.

  [ 크루스칼 알고리즘 알아보기(Click) ]

  [ 프림 알고리즘 알아보기(Click) ]

  [ 프림 알고리즘 알아보기2(Click) ]

 이 문제의 전체적인 풀이는, 위에서 말한 크루스칼 알고리즘과 프림 알고리즘을 구현하는 것이 대부분을 차지하고,

 따로 신경써야 할 부분은 없는 것 같다.

  단지, 구해야 하는 값은 "절약할 수 있는 최대비용" 이기 때문에, 본인은 입력과 동시에 모든 거리에 모든 불을

  켰을 때 드는 비용을 구해서, MST를 구현하는데 드는 비용과의 차이로 답을 도출해주었다.

  소스코드는 크루스칼 알고리즘을 이용한 방법과 프리 알고리즘을 이용한 방식 모두다 첨부하겠다.

[ 크루스칼 알고리즘을 사용한 소스코드 ]

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 200010
using namespace std;
 
int M, N, Total, Result, Answer;
int Parent[MAX];
bool Inp_Flag;
vector<pair<int, pair<int, int>>> Edge;
 
void Initialize()
{
    Edge.clear();
    Total = Result = 0;
    for (int i = 0; i < MAX; i++) Parent[i] = i;
}
 
void Input()
{
    cin >> M >> N;
    if (M == 0 && N == 0)
    {
        Inp_Flag = true;
        return;
    }
    for (int i = 0; i < N; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Edge.push_back(make_pair(c, make_pair(a, b)));
        Total = Total + c;
    }
}
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    else return Parent[A] = Find_Parent(Parent[A]);
}
 
bool SameParent(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    if (A == B) return true;
    return false;
}
 
void Union(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    
    Parent[B] = A;    
}
 
void Solution()
{
    sort(Edge.begin(), Edge.end());
    for (int i = 0; i < Edge.size(); i++)
    {
        int Cost = Edge[i].first;
        int Node1 = Edge[i].second.first;
        int Node2 = Edge[i].second.second;
 
        if (SameParent(Node1, Node2) == false)
        {
            Union(Node1, Node2);
            Result = Result + Cost;
        }
    }
    Answer = Total - Result;
}
 
void Solve()
{
    while (1)
    {
        Initialize();
        Input();
        if (Inp_Flag == true) return;
        Solution();
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 프림 알고리즘을 이용한 소스코드 ]

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 200010
using namespace std;
 
int M, N, Total, Result, Answer;
bool Visit[MAX];
bool Inp_Flag;
vector<pair<int, int>> Node[MAX];
 
void Initialize()
{
    Total = Result = 0;
    for (int i = 0; i < MAX; i++)
    {
        Visit[i] = false;
        Node[i].clear();
    }
}
 
void Input()
{
    cin >> M >> N;
    if (M == 0 && N == 0)
    {
        Inp_Flag = true;
        return;
    }
    for (int i = 0; i < N; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Node[a].push_back(make_pair(b, c));
        Node[b].push_back(make_pair(a, c));
        Total = Total + c;
    }
}
 
void Solution()
{
    priority_queue<pair<int, int>> PQ;
    for (int i = 0; i < Node[0].size(); i++)
    {
        int Next = Node[0][i].first;
        int Cost = Node[0][i].second;
        PQ.push(make_pair(-Cost, Next));
    }
 
    Visit[0] = true;
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        if (Visit[Cur] == false)
        {
            Visit[Cur] = true;
            Result = Result + Cost;
            
            for (int i = 0; i < Node[Cur].size(); i++)
            {
                int Next = Node[Cur][i].first;
                int nCost = Node[Cur][i].second;
 
                if (Visit[Next] == false) PQ.push(make_pair(-nCost, Next));
            }
        }
    }
    Answer = Total - Result;
}
 
void Solve()
{
    while (1)
    {
        Initialize();
        Input();
        if (Inp_Flag == true) return;
        Solution();
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}