[BOJ알고리즘, C++]#13418_학교 탐방하기, 최소 신장 트리, MST, 크루스칼

 

#1. 문제

https://www.acmicpc.net/problem/13418

 

---

 

#2. 풀이

 

1. 최소 신장 트리

[자료구조]#6_그래프

신장 트리는 그래프의 모든 정점을 최소한의 간선으로 순환 구조 없이 연결하는 부분 그래프를 의미합니다. 따라서, 최소 신장 트리는 가중치 그래프에서 간선들의 합이 최소가 되는 신장 트리입니다. 최소 신장 트리 알고리즘으로 크루스칼 알고리즘, 프림 알고리즘, 솔린 알고리즘이 있습니다. 

 

2. 크루스칼 알고리즘

[자료구조]#6_그래프

크루스칼 알고리즘은 최소 신장 트리 알고리즘 중 하나로 무방향 그래프의 각 간선들을 가중치 기준 오름차순 정렬하여, 최소 가중치를 갖는 간선을 선택하며 최소 신장 트리를 구성하는 알고리즘입니다. 일반적으로, 크루스칼 알고리즘은 간선 목록의 오름차순 정렬과 Union-Find 연산을 통해 구현됩니다. 크루스칼 알고리즘의 시간 복잡도는 최악의 경우 O(e log n)입니다.(e = 간선의 수, n = 정점의 수)

 

3. 최악? 내림차순 정렬, 최선? 오름차순 정렬

1. 먼저, 간선 목록을 구성할 때 오르막 길은 +1의 가중치를, 내리막 길은 0의 가중치를 갖도록 합니다.
2. 최악의 경우는 간선 목록을 내림 차순 정렬한 뒤 크루스칼을 수행하고, 최선의 경우는 간선 목록을 오름 차순 정렬한 뒤 크루스칼을 수행합니다.
3. 위 두 번의 크루스칼 수행의 결과 값을 빼주어 정답을 출력합니다.

 

---

 

#3. 코드

/*
    @문제: 피로도가 최대가 되는 경로 - 피로도가 최소가 되는 경로 구하기
    @설명:
        1. 간선목록 구성 시 오르막은 가중치를 1로, 내리막은 가중치를 0으로 변경
        2. 최대 신장 트리는 가중치 기준 내림차순 정렬 후 Kruskal 수행
        3. 최소 신장 트리는 가중치 기준 오름차순 정렬 후 Kruskal 수행
        4. 위 두 결과 값의 차이를 결과로 출력
*/

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

#define MAX 1001

// 간선 구조체 정의
struct Edge{
    int u,v,w;
    const bool operator<(const Edge& other)
    {
        return w<other.w;
    }

    const bool operator>(const Edge& other)
    {
        return w>other.w;
    }
};

int N, M, minST, maxST, res;
vector<Edge> edges;

int flip(int x)
{
    return x ^= 1;
}

// Union-Find 연산
int Find(int x, vector<int>& parent)
{
    if(parent[x] != x)
    {
        return parent[x] = Find(parent[x], parent);
    }
    else return x;
}

void Union(int rootX, int rootY, vector<int>& parent, vector<int>& ranks)
{
    if(ranks[rootX] > ranks[rootY])
    {
        parent[rootY] = rootX;
    }
    else if(ranks[rootY] > ranks[rootX])
    {
        parent[rootX] = rootY;
    }
    else{
        parent[rootY] = rootX;
        ranks[rootY]++;
    }
}

// 크루스칼 : 간선 목록 정렬에 대하여 isWorst가 참이면 가중치 기준 내림차순 정렬, 거짓이면 오름차순 정렬
int kruskal(vector<Edge> edges, bool isWorst)
{
    vector<int> parent(N+1);
    vector<int> ranks(N+1, 0);
    int fatigueVal=0;

    // 부모 목록 초기화
    for(int i=1; i<=N; ++i)
        parent[i] = i;

    // 간선 목록의 정렬 방식 선택
    if(isWorst) sort(begin(edges), end(edges), [](const Edge& a, const Edge& b){
        return a.w > b.w;
    });
    else sort(begin(edges), end(edges));

    for(const auto edge : edges)
    {
        int rootX = Find(edge.u, parent);
        int rootY = Find(edge.v, parent);

        if(rootX != rootY)
        {
            fatigueVal += edge.w;
            Union(rootX, rootY, parent, ranks);
        }
    }

    return pow(fatigueVal,2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i=0; i<=M; ++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        // 간선 목록 구성, 편의상 오르막은 0->1로 변경 + 내리막은 1->0으로 변경
        edges.push_back(Edge({u,v,flip(w)}));
    }

    //Reverse Kruskal (최대 스패닝 트리)
    res += kruskal(edges, true);
    //Kruskal (최소 스패닝 트리)
    res -= kruskal(edges, false);

    cout << res;

    return 0;
}

 

---