[BOJ][Python]4195 풀이

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

4195번: 친구 네트워크

from collections import defaultdict
import sys
ssr = sys.stdin.readline

def find(name):
    if uf[name] == name:
        return name
    else:
        uf[name] = find(uf[name])
        return uf[name]
    
def union(name1, name2):
    root1 = find(name1)
    root2 = find(name2)
    if root1 != root2:
        if rank[root1] < rank[root2]:
            uf[root1] = root2
            rank[root2] += rank[root1]
        elif rank[root1] == rank[root2]:
            uf[root1] = root2
            rank[root2] += rank[root1]
        else:
            uf[root2] = root1
            rank[root1] += rank[root2]
            
t = int(ssr())
for _ in range(t):
    uf = {}
    rank = defaultdict(lambda:1)
    f = int(ssr())
    for _ in range(f):
        people = ssr().rstrip().split()
        for i in people:
            if not i in uf.keys():
                uf[i] = i
        union(people[0], people[1])
        print(rank[find(people[1])])

최적화가 되어있다고 말하기는 힘든 코드인 것 같습니다. 아직 유니온 파인드를 배운지 이틀밖에 안되기도 했구요. 이번에는 그룹에 포함되어있는 사람이 몇명인지를 출력하는 내용입니다. 그래서 원래 rank를 이용해서 합치던게 생각이 나서 union을 할 때 각 그룹의 사람 수를 더해주는 걸로 구현했습니다. 원래 랭크가 트리의 깊이니까 union 할 때 마다 rank를 더해서 저장하면 사람수로 활용할 수 있겠죠(대신 초기값을 1로 해야 원하는 값이 나오니까 주의하구요).

 

어떻게 사람 수를 구할지 생각만 하면 나머지는 그냥 기본 유니온 파인드랑 다를게 없어서 그다지 어렵진 않았습니다.