[3780번] Corporative Network

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Union Find :: http://www.crocus.co.kr/683

2. 유니온 파인드 응용

일단 이 문제는 한국어 번역본이 없기에 말하고자 하는 내용을 요약해서 말하자면 다음과 같다.

E를 입력할 때는 현재 노드부터 루트 노드까지 거리를 출력하고

I를 입력할 때는 t1 노드와 t2 노드를 연결하되 t2노드가 t1노드의 부모가 되고 그 사이(t1~t2)의 길이를 저장해두어야 한다.

예제 입력을 통해 확인해보자.

1      -> 테스트 케이스
4      -> 필요없는 값
E 3    -> 현재 아무 정보가 없으니 처음 출력은 0이 나올 것이다.
I 3 1  -> 3->1로 연결하고 3의 길이 정보는 2가 된다.
E 3    -> 3의 길이정보를 출력하는 것이니 2가 출력된다.
I 1 2  -> 1->2로 연결하고 이때 1->2의 길이는 1인데 3->2의 길이도 업데이트 해야한다.
E 3    -> 3의 길이 정보는 3->2의 길이인 총 3이 된다.
I 2 4  -> 2->4로 연결하고 2의 길이는 2, 1의 길이는 1+2 = 3, 3의 길이는 3+2 = 5가 된다.
E 3    -> 3의 길이는 3->4인 5가 된다.
O      -> 종료

이제 우리가 확인해야 할 것은 유니온 파인드를 응용해야 하는 과정이다.

응용해야 할 부분은 다음과 같다.

1. 유니온(merge) 부분에서 부모를 루트로 찾아서 비교하는 것이 아닌 자신의 노드 t1과 다음 노드 t2간의 관계를 설정해준다.

2. 그리고 유니온 부분에서 t1과 t2간의 거리 정보를 t1에 입력해준다.

3. find 부분에서 루트로 이동하여 순차적으로 거리 정보를 업데이트 해준 후, 경로 압축을 해준다.

이 코드에서 의도하고자 하는 바는

I 3 1

I 1 2가 있다 생각하면

처음 I 3 1에서 3의 루트 및 부모는 1이 되고 경로는 2가 될 것이다.

그다음 I 1 2에서 1의 루트 및 부모는 2가 되고 경로는 1이 될 것이다.

마지막으로 E 3을 하면

3의 부모를 찾아가면 1이 되고, 1의 부모를 찾아가면 2가 된다.

2는 자기 자신이 루트이니 return 루트(2),자신(2) 를 해주고 1로 돌아온다.

1의 get.first(1의 루트)에는 2가있고 get.second(1의 부모)에는 2가 있다.

이것을 이용하여 len과 parent를 업데이트해준다.

이후 return 루트(2), 자신(1) 을 해주고 3으로 돌아온다.

3의 get.first(3의 루트)에는 2가 있고 get.second(3의 부모)에는 1이 있다.

이것을 이용하여 len과 parent를 업데이트 해준다.

결국 경로 압축, 거리 정보 업데이트를 모두 해 줌으로써 원하는 결과를 찾을 수 있다.

 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <math.h>
#include <memory.h>
 
#define swap(a,b){int t = a ; a = b; b = t;}
 
using namespace std;
 
typedef pair<int, int> pii;
 
int parent[20001], len[20001];
 
pii find(int u)
{
    if (u == parent[u])
        return pii(u, u);
 
    pii get = find(parent[u]);
 
    int root = get.first;
    int par = get.second;
 
    len[u] += len[par];
    parent[u] = root;
 
    return pii(root, u);
}
 
void merge(int u, int v)
{
    parent[u] = v;
 
    len[u] = abs(u - v) % 1000;
}
 
int main()
{
    int tCase;
 
    scanf("%d", &tCase);
 
    while(tCase--)
    {
        memset(parent, 0, sizeof(parent));
        memset(len, 0, sizeof(len));
 
 
        int n;
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++)
            parent[i] = i;
 
        while (1)
        {
            char op;
            scanf("%c", &op);
 
            if (op == 'O')
                break;
 
            else if (op == 'E')
            {
                int val;
                scanf("%d", &val);
 
                find(val);
                printf("%d\n", len[val]);
            }
 
            else if (op == 'I')
            {
                int t1, t2;
                scanf("%d %d", &t1, &t2);
 
                merge(t1, t2);
            }
        }
    }
    return 0;
}
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>