[백준 13418] 학교 탐방하기 - c++로 구현한 최소 스패닝 트리

문제 개요

• 문제 번호: 13418
• 제목: 학교 탐방하기
• 난이도: 골드 3
• 링크: 백준 13418번

---

문제 설명

학교안에 있는 모든 건물에 대한 이동 경로를 짜는 코드를 작성해야한다.
최소한의 길을 선택해 모든 건물을 방문해야한다.

길의 종류: 오르막길과 ( 0 ) 내리막길 ( 1 )

입구 번호는 0번

오르막길을 K번 오르면 피로도는 K^2

피로도 계산은 최초 계산될 때 한번만 반영

건물의 갯수: N (1 <= N <= 1000)

도로의 갯수: M (1 <= m <= N*(N-1)/2)

A 건물에서 B 건물까지 C (0은 오르막길 1은 내리막길)

최악의 경로를 이용했을때 피로도와 최적의 경로를 이용했을때 피로도의 차이를 구해라

---

접근 방법

1. 모든 건물을 방문하는 경로를 이어야하기 때문에 최소 스패닝 트리를 이용한다.
2. 간단하게 Union-Find를 이용한 크루스칼 알고리즘을 사용했다.
3. 이때 가중치는 0과 1이기 때문에 최선인 경우와 최악인 경우 0일때 카운트를 해주고 나온 값을 제곱해 차이를 구하면 된다.

---

구현 코드

#include<iostream>
#include<algorithm>
#include<tuple>
using namespace std;

int n, m;
tuple<int, int, int> edge[500000];
int bp[1005];
int wp[1005];

int find (int x, int p[]){
    if(p[x] == 0) return x;
    return p[x] = find(p[x], p);
}

bool is_diff_group(int a, int b, int p[]){
    a = find(a, p);
    b = find(b, p);

    if(a == b) return 0;
    else if(a < b) p[b] = a;
    else p[a] = b;
    return 1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {c, a, b};
    }

    sort(edge+1, edge+m+1);

    int worst = 0;
    int best = 0;
    int a, b, c;
    tie(c, a, b) = edge[0];
    if(is_diff_group(a, b, wp) && c == 0) worst++;
    if(is_diff_group(a, b, bp) && c == 0) best++;

    for(int i = 1; i <= m; i++){
        int wa, wb, wc; // worst인 경우
        int ba, bb, bc; // best인 경우
        tie(wc, wa, wb) = edge[i];
        tie(bc, ba, bb) = edge[m-i+1];

        if(is_diff_group(wa, wb, wp) && wc == 0) worst++;
        if(is_diff_group(ba, bb, bp) && bc == 0) best++;
    }

    cout << abs(worst*worst - best*best);
}