BOJ 1647 도시 분할 계획

문제

$N$개의 집과 $M$개의 도로가 주어졌을 때, 마을을 두 개의 분리된 컴포넌트로 분할하며 도로 유지비의 합을 최소화하는 문제입니다. 각 마을 내부의 집들은 서로 연결되어 있어야 한다는 점이 핵심입니다.

복잡도 분석

• 시간 복잡도: $O(M \log M)$
  • 간선 정렬: $O(M \log M)$
  • Kruskal 알고리즘 (Union-Find): $O(M \cdot \alpha(N))$, 여기서 $\alpha$는 아커만 역함수로 사실상 상수입니다.
  • 최종적으로 정렬이 전체 시간 복잡도를 지배합니다. ($M=10^6$일 때 약 $2 \times 10^7$ 연산)
• 공간 복잡도: $O(N + M)$
  • 간선 정보 저장: $O(M)$
  • Union-Find 배열(parent, rnk): $O(N)$

접근법

최소 신장 트리(Minimum Spanning Tree, MST) 문제. 크루스칼 알고리즘으로 MST 구성하고, 이 문제의 경우 2개 마을로 분할을 원하고 있으므로 연결한 간선 중 가중치가 큰 간선을 저장해뒀다가 마지막에 cost에서 제외하면 된다.

풀이

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

int n,m;
struct Edge{
    int u,v,c;
    bool operator<(const Edge &other) const{
        return c<other.c;
    }
};
vector<Edge> g;
vector<int> parent;
vector<int> rnk;

int _find(int a){
    if(parent[a]==a) return a;
    return parent[a] = _find(parent[a]);
}

bool _union(int a, int b){
    a = _find(a);
    b = _find(b);
    if (a==b) return false;

    if (rnk[a] > rnk[b]){
        int tmp=a;a=b;b=tmp;
    }
    parent[a] = b;
    if (rnk[a]==rnk[b]){
        rnk[b]++;
    }
    return true;
}

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;
        g.push_back({a,b,c});
    }
    rnk.resize(n+1,0);
    for(int i=0;i<n+1;i++){
        parent.push_back(i);
    }

    sort(g.begin(),g.end());

    int connected = 0;
    int cost = 0;
    int mx = 0;
    for(int i=0;i<size(g);i++){
        int a = g[i].u;
        int b = g[i].v;
        int c = g[i].c;
        if (_union(a,b)){
            connected++;
            cost += c;
            mx = max(mx,c);
        }
        if (connected==n-1) break;
    }
    cout << cost-mx;

    return 0;
}

유니온 파인드 부분 실수한거 제외하고는 한번에 성공함.