문제

[백준] 친구 네트워크 (Gold 2)

요약

친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하라. 친구 네트워크란, 친구 관계만으로 이동할 수 있는 사이를 말한다.

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 출력하라.

분류

  • 분리 집합
  • 해시 맵

풀이

1. 내 풀이 (분리 집합, 해시 맵)

분리 집합을 이용해, 친구 관계를 관리하자. 일반적으로 분리 집합을 다룰 때 집합의 부모 노드를 배열로 관리한다. 이는 각 노드가 인덱싱되어(번호가 매겨져) 있기에 배열 접근을 O(1)의 시간복잡도로 할 수 있다. 그러나, 이 문제에서는 각 노드가 문자열로 정의되고 번호가 매겨져 있지 않기 때문에 부모 노드를 배열로 관리한다면 O(N)의 시간복잡도를 갖게 된다. 따라서 노드의 이름(친구 이름)을 KEY로, 부모 노드를 VALUE로 하는 해시 맵으로 노드를 관리하는 것이 적절하다. 해시 맵은 O(1)~O(N)의 시간복잡도를 갖는다.

또, 부모 노드 마다 자식 노드의 수(친구 네트워크에 있는 친구의 수)도 기록해 주어야 하기에, 자식의 수를 기록하는 해시맵도 하나 만들어 주었다. UNION 연산을 진행하며 각 트리의 노드 수도 더해준다.

import sys
input = sys.stdin.readline


def find(x):
    global parent
    global cnts
    if x not in parent:
        parent[x] = x
        cnts[x] = 1
        return x
    if x != parent[x]:
        parent[x] = find(parent[x])

    return parent[x]


def union(s1, s2):
    global parent
    global cnts
    if s1 < s2:
        parent[s2] = s1
        cnts[s1] += cnts[s2]
        return cnts[s1]
    else:
        parent[s1] = s2
        cnts[s2] += cnts[s1]
        return cnts[s2]


t = int(input())
for _ in range(t):
    n = int(input())
    parent = {}
    cnts = {}

    for _ in range(n):
        a, b = input().rstrip().split()

        s1 = find(a)
        s2 = find(b)

        if s1 != s2:
            cnt = union(s1, s2)
            print(cnt)
        else:
            print(cnts[s1])