백준 4195 : 친구 네트워크 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def Find(x):
    if parent[x]!=x:
        parent[x]=Find(parent[x])
    return parent[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a!=b:
        parent[b]=a
        number[a]+=number[b]
    print(number[a])
T=int(input())
for i in range(T):

    F=int(input())

    parent,number={},{}

    for j in range(F):
        a,b=input().split()
        if a not in parent:
            parent[a]=a
            number[a]=1
        if b not in parent:
            parent[b]=b
            number[b]=1

        Union(a,b)

📌 어떻게 접근할 것인가?

유니온 파인드와 비슷하지만 다른점이 2가지가 있습니다.

• 정수가 아니라 문자열을 입력받는다
• 두 노드가 같은 집합인지가 아니라 관계의 수를 구한다.

일단 문제를 해결하기 위해서 2개의 딕셔너리를 사용하였습니다.
parent 는 문자열 집합을 담당하고 number 은 관계의 수를 담당합니다..

$Find$ 함수는 유니온 파인드에서 사용하는 그대로 사용하면 되고 $Union$ 에서 합치는 과정에
만약 서로 다른 집합이라면 관계의 수를 구해야 하기 때문에 parent[b]=a 를 통해 서로 연결 해준뒤에
그 길이 또한 number[a]+=number[b] 를 통해 모든 관계의 수를 구해줍니다.

이후 number[a] 를 출력하면 모든 관계의 수를 구할 수 있습니다.