[ BOJ 백준 17398번 - 통신망 분할 ] 해설 및 코드

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

 

목적

통신망을 주어진 순으로 나누는데 필요한 비용을 구하자.

 

접근법

1. 통신망을 구축해 나가는데에는 disjoint-set을 이용하면 될 것이란 생각은 든다. 하지만 해당 알고리즘으로 합친 집합을 분리하는 것은 불가능(?방법이 있을 수도 있습니다...)하다. 하지만, 분리하는 과정을 거꾸로 한다면 union-find 만으로 해결이 가능하다.

 

2. 제거해야 할 열결 번호를 저장하고, 일단은 제거할 번호 리스트에 없는 연결만 수행하자. 그리고 제거할 번호 리스트의 역순으로 연결을 수행하며 비용을 연산하면 된다.

 

3. 하마터면, link/cut tree 자료구조를 공부할 뻔.... 아직은 미뤄두고 싶은...

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
 
const int LEN = 1e5+1;
int p[LEN],e[LEN][2],r[LEN];
bool chk[LEN]{};
 
int find(int x) {
    return p[x] < 0 ? x : p[x] = find(p[x]);
}
 
void merge(int x, int y) {
    if (p[x] > p[y]) swap(x, y);
    p[x] += p[y];
    p[y] = x;
}
 
int main() {
    ios_base::sync_with_stdio(0);
 
    memset(p, -1, sizeof(p));
    int n, m, q,tmp; 
    cin >> n >> m >> q;
    f(i, 1, m)cin >> e[i][0] >> e[i][1];
    fr(i, q, 1) cin >> r[i], chk[r[i]] = true;
    
    f(i, 1, m) if(!chk[i]){
        int x = find(e[i][0]), y = find(e[i][1]);
        if (x != y)merge(x, y);
    }
 
    ll ans = 0;
    f(i, 1, q){
        int x = find(e[r[i]][0]), y = find(e[r[i]][1]);
        if (x == y)continue;
        ans += (p[x] * p[y]);
        merge(x, y);
    }
    cout << ans;
 
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.