BaekJoon3780_네트워크 연결

문제

풀이

이 문제는 문제를 푸는데는 오래 걸리지 않았지만 문제를 이해하는데 시간이 좀 오래 걸렸다.
각 기업들은 숫자로 구분되고 자체적인 통신센터가 존재한다.
각 기업의 서버들을 네트워크로 연결하여 단일 통신센터에서 관리가능하게 구성하기로 하였는데 그 방법은 다음과 같다.
1. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
2. 클러스터 B를 제공하는 기업 J를 고른다.
3. I와 J를 통신 라인으로 연결하고 이때 I와 J를 잇는 라인의 길이는 |I-J|(mod 1000)이다.
4. 위 방식으로 합친 클러스터는 B의 센터를 통해 제공된다.

아니 무슨 클러스터니 뭐니 하면서 정신이 혼미했는데 간단하게 처음 각 기업들을 루트로 보고 서로 연결하는 거다. 이때 연결하는 순서는 I A B 면 A를 B의 루트에 연결하는 것이고, 이때 각 기업을 연결하는 간선의 길이는 기업의 숫자들을 빼고 1000으로 나눈 나머지 값이다.

그럼 union-find를 이용해 각 기업들의 부모노드(루트 노드)를 갱신해주고 기업으로 부터 루트노드까지의 거리를 출력해주면 된다.

코드에서 renew() 함수가 union-find의 find함수라고 생각하면 된다. dist 배열은 각 기업에서 센터까지의 거리를 저장해둔 배열이고 처음 각 기업의 센터는 자기 자신이므로 초기값은 모두 0이다.

풀이코드

import sys
input = sys.stdin.readline

t = int(input())

def renew(a):
    if root[a] == a:
        return a
    else:
        temp = renew(root[a])
        dist[a] += dist[root[a]]
        root[a] = temp
        return temp
    
for i in range(t):
    n = int(input())
    dist = [0] * (n+1)
    root = [i for i in range(n+1)]

    while True:
        order = input().split()
        if order[0] == 'E':
            renew(int(order[1]))
            print(dist[int(order[1])])
        elif order[0] == 'I':
            dist[int(order[1])] = abs(int(order[2]) - (int(order[1]))) % 1000
            root[int(order[1])] = int(order[2]) 
        else:
            break