백준) 3780 네트워크 연결

3780. 네트워크 연결

문제

종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.

어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.

1. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
2. 클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다.
3. I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 |I – J|(mod 1000)이다.
4. 위 방식을 통해 클러스터 A와 B는 새로운 클러스터로 합쳐지며, 이 클러스터는 B의 센터에 의해 제공된다.

이러한 병합 과정을 거치던 중에, 각 기업에서 현재 센터까지 연결되는 라인의 길이가 총 얼마나 되는지에 관한 문의가 들어왔다. 서현이를 위해 병합하는 과정과 그 과정에서 통신센터와 각 기업을 잇는 라인의 길이를 구하는 프로그램을 작성해보자.

입력

입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(5 ≤ N ≤ 20,000)이 주어진다. 다음은 몇 개의 줄에 걸쳐 아래 두 가지 종류의 명령어가 들어온다.

• E I – 기업 I와 현재 I의 센터까지의 거리를 출력한다. 
• I I J – 센터 I를 기업 J에 연결한다.

각 테스트케이스의 끝에는 단어 O가 주어진다. 각 테스트케이스에서 명령어의 총 개수는 200,000개를 넘지 않으며, 그중 I 명령어의 개수는 N개보다 작다.

출력

E 명령어가 들어올 때마다 한 줄에 해당 거리를 출력한다.

예제 입력 

1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O

예제 출력 

0
2
3
5

1. 접근

각 기업별로 서버를 갖고 있다. 서버는 네트워크로 연결될 수 있고, 네트워크에는 센터 서버가 있다.

따라서 현재 기업마다의 센터는 단일 네트워크이자, 센터 서버이다.

이제 네트워크들을 I 명령어로 연결하고자 한다.

I 1 2 라면, 센터 서버인 1서버와, 2서버를 연결한다. 주의할 점은 첫번째 서버는 반드시 센터 서버이고,

두번째 서버는 그 서버가 속한 네터워크의 센터 서버가 아닐 수도 있다.

또한 연결된 이후에는, 두 네트워크는 하나의 네트워크가 되며, 센터 서버는 두번 째 서버가 담당한다.

우리는 서버들을 노드로 표현할 수 있으며, 서버들의 종속관계를 간선으로 표현할 수 있다.

간선의 크기는 |i - j|(mod 1000)으로 지정된다.

이때 한 기업이 주어지면, 기업의 서버에서, 그 서버의 센터 서버까지의 경로의 길이 합을 구해야 한다.

그래프적인 방법으로 접근해보자.

2. 풀이

네트워크는 집합으로, 센터는 루트 노드로 생각한다면, 바로 디스조인트-셋을 사용할 생각이 든다.

센터노드는 하나이므로, 노드에서 나가는 간선은 최대 한개이기 때문이다.

하지만 문제는 길이 합을 구해야 하기 때문에, 매번 경로를 탐색한다면,

명령어의 수(200,000) * 최악의 경로(20,000)으로 시간초과가 날 것이다.

따라서 디스조인트의 연산을 활용하여, 연결 시 마다 네트워크의 종속관계를 갱신해주고, 길이도 갱신해보도록 하자.

연결을 담당하는 union()시 i는 기존의 센터이고, j는 새로운 센터가 될 서버이므로 매우 쉽게 연결과 길이 정의가 가능하다.

이제 find()가 길이 합을 계산해주는 역할을 해야 한다. find는 부모를 재귀적으로 따라가서 최종적으로 루트노드를 반환해주는 연산이다.

우리가 원하는 연산은 센터를 제외한 나머지 노드의 부모를 센터로 지정하고, 길이도 갱신해줘야 한다.

또한 x서버에서 센터까지 가는 경로는 유일하므로, find를 조금 바꿔주면 가능하다.

재귀적으로 루트노드 갱신을 해주는 원래 기능에, 길이 갱신만 추가하면 된다.

len[x] += len[parent[x]]

다음 예시로 어떤 동작을 해야하는지 알아보자.

I 1, 2

I 2, 3

E 1

위와 같은 경우에, union()을 두번 수행한 결과 1번 노드는 2번 노드를, 2번 노도는 3번 노드를 가리키고 있을 것이다.

이제 find(1)을 수행하면, 1번 노드는 3번 노드를 가리켜야 하고, 길이는 2번 노드의 것을 추가하여 갱신되어야 한다.

3. 코드

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
 
typedef pair<int, int> p;
int t, n, a, b, c, i;
int parent[20001];
int len[20001];
 
int find(int x) {
    if (parent[x] == x)
        return x;
    else {
        int tmp = find(parent[x]);
        len[x] += len[parent[x]];
        parent[x] = tmp; 
 
        return tmp;
    }
}
 
void unite(int x, int y) {
    len[x] = abs(x - y) % 1000;
    parent[x] = y;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 0; i <= n; ++i) {
            parent[i] = i;
            len[i] = 0;
        }
        while (1) {
            scanf(" %c", &c);
            if (c == 'E') {
                scanf("%d", &a);
                find(a);
                printf("%d\n", len[a]);
            }
            else if (c == 'I') {
                scanf("%d %d", &a, &b);
                unite(a, b);
            }
            else
                break;
        }
    }
    return 0;
}

재귀를 알맞게 구성해내는 경험이 더러 필요하다.