BOJ 4195 - 친구 네트워크

문제

백준 온라인 저지 - 4195번

풀이 과정

친구 관계를 갱신하면서 친구 네트워크에 몇 명이 있는지 구하는 문제입니다.

이는 직관적으로 유니온 파인드 자료구조를 사용해서 해결할 수 있다는 것을 알 수 있습니다.
친구 관계가 추가될 때마다 그 둘을 union 해준 뒤 생성된 집합의 크기를 반환해주면 됩니다.
이때 입력으로 문자열이 주어지므로 해싱 을 통해 접근할 수 있도록 딕셔너리 자료형을 사용한 것에 유의합니다.

코드

import sys


def union(u, v):
    u, v = find(u), find(v)

    if u == v:
        return
    if rank[u] > rank[v]:
        u, v = v, u
    parent[u] = v
    if rank[u] == rank[v]:
        rank[v] += 1
    size[v] += size[u]


def find(u):
    if parent[u] == u:
        return u
    parent[u] = find(parent[u])
    return parent[u]


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        rank = {}
        parent = {}
        size = {}

        F = int(input())
        for _ in range(F):
            targets = list(sys.stdin.readline().split())
            for target in targets:
                if target not in parent:
                    parent[target] = target
                    size[target] = 1
                    rank[target] = 1

            union(targets[0], targets[1])
            print(size[find(targets[0])])