BOJ - 네트워크 연결(3789)

Disjoint Set 문제이며 유니온 파인드(Union-Find)를 사용해서 해결할 수 있는 문제입니다. 중요한 부분은 find를 할 때 기존 경로 압축(path compression)을 하면서 거리도 업데이트 해줘야 합니다. merge 할 때는 최상위 노드를 따로 찾을 필요 없이 입력으로 들어온 두 노드를 바로 연결 해주면 됩니다.

라인 길이

// define
#define MAX 200010

// distance to center
int dist[MAX];

// get distance
int distance(int a, int b) {
    int dist = a > b ? a - b : b - a;
    return dist % 1000;
}

유니온 파인드

int parent[MAX];

int find(int n) {
    if (parent[n] == 0) return n;
    int p = find(parent[n]);

    //// 길이 업데이트 ////
    dist[n] += dist[parent[n]];
    
    parent[n] = p;
    return p;
    
}

void merge(int a, int b) {
    dist[a] = distance(a, b);
    parent[a] = b;
}

메인 함수

#include <stdio.h>
int main() {

    int T;
    scanf("%d", &T);

    while(T--) {
        // initialize
        for (int i = 0; i < MAX; i++) {
            dist[i] = 0;
            parent[i] = 0;
        }

        int N;
        scanf("%d", &N);
        while(true) {

            char command;
            scanf(" %c", &command);
            if (command == 'O') {
                break;
            }

            if (command == 'E') {
                int i;
                scanf("%d", &i);
                find(i);
                printf("%d\n", dist[i]);
            } else {
                int i, j;
                scanf("%d %d", &i, &j);
                merge(i, j);
            };
        }
    }
    return 0;
}