[Beakjoon] 4195. 친구 네트워크

🔗 Problem Link

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

---

❔Thinking

• 친구 관계가 주어지면, 해당 친구 네트워크에 속한 인원 수를 반환한다.
• 친구 네트워크는, root가 같은 사람들을 뜻한다.

---

💻Solution

import sys
input = sys.stdin.readline

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

def union(a, b, parent, size):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a != b:
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

T = int(input().rstrip())
answer = []
for _ in range(T):
    F = int(input().rstrip())
    people_dict = {}
    parent = []
    size = []

    for _ in range(F):
        f1, f2 = input().split()
        
        if f1 not in people_dict:
            people_dict[f1] = len(parent)
            parent.append(len(parent))
            size.append(1)
        if f2 not in people_dict:
            people_dict[f2] = len(parent)
            parent.append(len(parent))
            size.append(1)
        
        union(people_dict[f1], people_dict[f2], parent, size)
        
        root = find_parent(people_dict[f1], parent)
        answer.append(size[root])

for a in answer:
    print(a)

---

🗝️keypoint

1. 친구의 친구를 하나의 네트워크로 계산하려면, union을 새로운 관계가 생길때마다 전부 반복해야한다. (시간초과 발생)
2. size 배열은 해당 root 집합의 인원수를 확인할 수 있다. union시 root의 size에 해당 친구가 속한 인원을 전부 더해간다.