[C++] 네트워크 연결 [백준 3780]

Disjoint_Set의 개념으로 길이 배열을 한가지 더 선언해주어서 절대 차이만큼만 

더해주면서 저장하면 되는 것이었다. 

find 와 init 과정에서 parent 배열과 길이를 저장할 배열을 따로 만들어주었다. 

find를 호출할때마다 해당 노드의 루트노드를 탐색하고 루트노드까지의 길이를 해당 인덱스의

길이 배열에 저장해주었다. 

(어렵게 생각하기보단 풀리지 않는다면 Disjoint_set의 과정을 완벽히 이해해보시길 바랍니다.)

그래도 이해가 가지않는다면 댓글과 쪽지를 주세요!

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

3780번: 네트워크 연결

문제 종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다. 어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다. 클러스터 B를 제공하는 기업 J를 고른다.

www.acmicpc.net

<CODE>

//pda_pro12
#include<iostream>
#include<algorithm>
 
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define N_ 20001
#define mod (int)1e3
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pll;
typedef double db;
 
int n, m, t, par[N_], len[N_];
 
void init() {
    for (int i = 1; i <= n; i++)
        par[i] = i, len[i] = 0;
    return;
}
 
int find(int x) {
    if (x == par[x])
        return x;
    else {
        int tmp = find(par[x]); 
        len[x] += len[par[x]]; 
        par[x] = tmp; 
        return tmp;
    }
}
 
void Merge(int x, int y) {
    len[x] = abs(x - y) % mod; 
    par[x] = y; 
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while (t--) {
        cin >> n;
        init(); 
        char inp; int a, b;
        while (1) {
            cin >> inp;
            if (inp == 'O')
                break; 
            else if (inp == 'E') {
                cin >> a;
                find(a); 
                cout << len[a] << '\n';
            }
            else if (inp == 'I') {
                cin >> a >> b;
                Merge(a, b);
            }
        }
    }
    return 0;
}