[백준][C++] 13418 학교 탐방하기

www.acmicpc.net/problem/13418

13418번: 학교 탐방하기

 

 

 

알고리즘 종류

    - MST

 

 

 

사고 과정

    - 간선은 오르막길과 내리막길 뿐이기 때문에 비용을 계산하기 쉽게 오르막길은 1, 내리막길은 0으로 설정한다.

    - 간선을 오름차순과 내림차순으로 정렬해서 각각 MST 알고리즘을 적용한다.

    - 두 경우에서 나온 합을 이용해서 피로도 차이를 계산한다. 본인은 오르막길 비용을 1로 했기 때문에 오르막길의 개수^2은 피도로가 나온다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
 
int N, M;
int worstSum = 0;
int bestSum = 0;
 
vector<pair<pair<int, int>, int> > edges;
int parents[1001];
 
 
bool cmp_increase(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second < b.second;
}
 
bool cmp_decrease(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second > b.second;
}
 
int getParent(int x){
    if(parents[x] == x) return x;
    return parents[x] = getParent(parents[x]);
}
 
void unionParents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a > b) parents[b] = a;
    else parents[a] = b;
}
 
void solution(){
    
    // best
    // 최고의 경우, 간선을 오름차순으로 정렬했을 때 
    sort(edges.begin(), edges.end(), cmp_increase);
    for(int i=0; i<=N; i++) parents[i] = i;
    
    for(int i=0; i<edges.size(); i++){
        if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
            bestSum += edges[i].second;
            unionParents(edges[i].first.first , edges[i].first.second);
        }
    }
    
    // worst
    // 최악의 경우, 간선을 내림차순으로 정렬했을 때  
    sort(edges.begin(), edges.end(), cmp_decrease);
    for(int i=0; i<=N; i++) parents[i] = i;
    
    for(int i=0; i<edges.size(); i++){
        if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
            worstSum += edges[i].second;
            unionParents(edges[i].first.first , edges[i].first.second);
        }
    }
    
    // 2를 제곱해서 차를 출력  
    cout << pow(worstSum, 2) - pow(bestSum, 2);
    
}
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> M;
    
    int A, B, C;
    cin >> A >> B >> C;
    // 입구에서 첫 건물까지 오르막이면 +1, 아니면 +0 
    if(C==0){
        worstSum += 1;
        bestSum += 1;
    }
    else{
        worstSum += 0;
        bestSum += 0;
    }
    
    for(int i=0; i<M; i++){
        cin >> A >> B >> C;
        if(C==0) edges.push_back({{A, B}, 1});
        else edges.push_back({{A, B}, 0});
    }
    
    solution();
}
 
 
 

 

 

 

시행착오