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

 

 

 

알고리즘 종류

    - MST

 

 

 

사고 과정

    - 일반적인 MST으로 해결하면 될 것 같았다.

        1. 입력된 간선의 비용을 오름차순으로 정렬한다.

        2. 사이클인지 확인하고 아니면 간선을 선택하여 연결 비용에 추가한다.

        3. 2번에서 MST를 구하면, 총 비용에서 연결에서 구한 최소 비용을 뺀다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int totalCost = 0;
 
int parents[200001];
 
struct Edge{
    int from, to;
    int cost;
};
 
vector<Edge> edges;
 
bool cmp(Edge a, Edge b){
    return a.cost < b.cost;
}
 
int getParent(int a){
    if(parents[a] == a) return a;
    return parents[a] = getParent(parents[a]);
}
 
bool isCycle(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a==b) return true;
    else return false;
}
 
void unionParents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a > b) parents[a] = b;
    else parents[b] = a;
}
 
 
void kruskal(){
    
    sort(edges.begin(), edges.end(), cmp);
    
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        if(!isCycle(edges[i].from, edges[i].to)){
            unionParents(edges[i].from, edges[i].to);
            sum += edges[i].cost;
        }
    }
    cout << totalCost - sum << endl;
}
 
int main(void){
    
    // 여러 테스트 케이스가 주어진다.
    while(1){
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        
        // 초기화  
        totalCost = 0;
        edges.clear();
        for(int i=0; i<n; i++) parents[i] = i;    
        
        // 입력  
        for(int i=0; i<m; i++){
            Edge e;
            cin >> e.from >> e.to >> e.cost;
            edges.push_back(e);
            totalCost += e.cost;
        }
    
        kruskal();
    }
    
    return 0;
}

 

 

 

시행착오

    - 이 문제는 아니지만, 삼성 SW 역량 테스트 기출 문제를 풀면 테스트 케이스를 생각해야 한다. 이것이 내가 백준에서 넘어갈 때 처음으로 고려해야 할 것이었다. 즉, while로 테스트 케이스를 받아주고, 사용한 것들을 초기화 해주어야 했다. 여기서 초기화와 다른 이유 때문에 1시간을 고행을 넘었다. 가장 애먹인 부분은 cout << totalCost - sum << endl; 이다. 결과를 출력 할 때 endl;를 붙여주지 않았다. 그래서 계속 틀렸다... 정말 다양한 짓을 다 했다...