[MST, UnionFind] BOJ 1647 도시 분할 계획

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

1647번: 도시 분할 계획

 

문제 해결 알고리즘

 

크루스칼 알고리즘으로 풀어준다.

이 때 두 도시로 분할하는 것이므로 마지막 간선이 제일 큰 값을 가질테니까 마지막 간선의 값만 빼주면 최소값이 나온다.

 

그리고 find_parent함수를

 

int find_parent(int x){
    if(parent[x] == x) return x;
    else return find_parent(parent[x]);
}

 

이런 식으로 짜게 된다면 시간초과를 피할 수 없다.

왜냐면 모든 값들을 전부 재귀로 돌려줘야하기 때문이다.

 

그래서 unionfind 알고리즘을 이용해주어야한다.

 

int find_parent(int x){
    if(parent[x] == x) return x;
    else return parent[x] = find_parent(parent[x]);
}

 

위의 방식대로 부모 노드로 올라갈 때마다 전부 기록을 해주므로써 재귀 개수를 확연히 줄여줄 수 있다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, M;

vector<pair<int, pair<int, int>>> graph;
int parent[100001];
bool flag = false;
ll result = 0;

int find_parent(int x){
    if(parent[x] == x) return x;
    else return parent[x] = find_parent(parent[x]);
}

void unionVertex(int u, int v){
    flag = false;

    u = find_parent(u);
    v = find_parent(v);

    if(u == v) return;
    else{
        flag = true;
        parent[u] = v;
    }
}

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;

        graph.push_back({c, {a, b}});
    }

    for(int i=1;i<=N;i++) parent[i] = i;
    
    sort(graph.begin(), graph.end());

    int last;

    for(int i=0;i<graph.size();i++){

        unionVertex(graph[i].second.first, graph[i].second.second);

        if(flag == true) {
            result += graph[i].first;
            last = graph[i].first;
        }
    }

    result -= last;
    

    cout << result;
}