[ BOJ 백준 3780번 - 네트워크 연결 ] 해설 및 코드

 

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

목적

통신센터와 각 기업을 잇는 라인의 길이를 구하자.

 

접근법

1. disjoint-set으로 접근하는데, 라인의 길이 정보를 어떻게 처리할 지가 관건이다. 

 

2. 병합하는 과정은 클러스터 A의 센터가 클러스터 B의 기업들 중 하나에 연결되어 진행된다. 따라서 클러스터 A의 기업-센터 사이의 거리만 갱신해주면 된다. (클러스터 B의 기업-센터 사이의 거리는 변함이 없으므로...)

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int MAXN = 2e4 + 1;
int p[MAXN], len[MAXN];
 
int find(int x) {
    if (x == p[x])return x;
    int tmp = find(p[x]); 
    len[x] += len[p[x]];
    return p[x] = tmp;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        f(i, 1, n)p[i] = i, len[i] = 0;
        char ch;
        while (cin >> ch, ch != 'O') {
            if (ch == 'E') {
                int i; cin >> i;
                find(i);
                cout << len[i] << '\n';
            }
            else {
                int i, j; cin >> i >> j;
                len[i] = abs(i - j) % 1000;
                p[i] = j;
            }
        }
    }
    
    return 0;
}
 
 

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

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