[python3] 백준 4195 (친구 네트워크, 유니온 파인드)

문제는 아주 심플하다. 소셜네트워크를 구성할때 서로 친구가 될때마다 해당 네트워크에 몇명이 속하는지 알아내면 된다.
테스트 케이스의 범위는 주어지지 않았지만 F의 값이 100,000으로 주어졌다. 그럼 테스트 케이스 * 100,000으로 상당히 연산량이 클것으로 예상된다. 또한 DFS를 통해 구성된 네트워크의 노드 갯수를 센다고 가정한다면 100,000 * O(N) 정도의 시간 복잡도가 걸리는데 만약 N이 100,000이 된다면 너무 시간복잡도가 크다. 즉, 매번 탐색하는 방식으로는 구할 수가 없다.
그럼 A라는 친구가 어디 네트워크에 속하고, 네트워크의 크기는 어느정도인지 한번에 안다면 우리는 testcase*100,000의 연산만으로 정답을 구할 수 있다. 딱 냄새가 난다 네트워크에 속하고 머시기 어쩌고는 유니온 파인드이다.

그럼 기존의 유니온 파인드와 코드는 조금 달라질 것이다. 그러나 그림을 그리면 아주 쉬워진다.

Node number는 네트워크에 포함되는 노드의 수를 의미한다. 처음에는 자신만 포함하기 때문에 1을 가진다.
Parent는 말그대로 해당 노드의 부모 노드를 의미하다. 처음에는 자신을 부모로 둔다.

이후 간선의 정보를 확인하며 표를 갱신한다. 서로의 부모 노드가 다른경우 작은 노드를 부모노드로 두게 하여 서로의 루트 노드가 가지는 네트워크 수만큼 갱신해준다. (*일관성을 위해 작은노드를 무조건 부모 노드로 두게 한다.) 이후 같은 노드를 추가하며 해당 과정을 반복한다. 

위와 같이 1,2,3,4가 이미 연결되어 있지만 2-4를 연결하는 경우가 존재한다. 이러한 경우 둘다 루트 노드가 1이기 때문에 Node Number와 Parent를 갱신시키지 않고 넘어간다.

이러한 규칙을 지키며 코딩을 진행하면 된다. 기존 유니온 파인드는 리스트를 사용했지만 이번 문제는 문자열로 구분해야하기 때문에 dictionary를 2개 만들어서 사용했다.

"""
유니온 파인드의 심화 버전 느낌?
기준은 알파벳 순서로 기준잡기

Group Number dic
Parent dic
"""

from collections import defaultdict
import sys
#input = sys.stdin.readline

P = {}
N = {}


def find(node):  # 루트 노드 찾아주기
    if P[node] == node:
        return node
    P[node] = find(P[node])  # 상위의 모든 노드를 찾아서 갱신시켜준다.
    return P[node]  # 찾은 부모 노드를 반환해준다.


def union(A, B):
    A = find(A)  # 루트 노드를 찾는다.
    B = find(B)

    if A == B:
        return N[A]
    elif A < B:
        P[B] = A
        N[A] += N[B]
        return N[A]
    else:
        P[A] = B
        N[B] += N[A]
        return N[B]


T = int(input())
for i in range(T):
    F = int(input())

    N = {}
    P = {}
    for j in range(F):
        A, B = input().split()
        # 초기화 하기
        if A not in P:
            P[A] = A
        if B not in P:
            P[B] = B
        if A not in N:
            N[A] = 1
        if B not in N:
            N[B] = 1
        # 합치기
        result = union(A, B)
        print(result)