백준-4195-친구 네트워크

문제

친구 네트워크

풀이

문제조건 해석

Union-Find 응용 문제이다.

MST는 edge의 가중치 값을 다루는 반면, 이 문제는 disjoint set에 있는 원소 수를 구해야 한다.

알고리즘

Union-Find를 이용해야 한다.

• count 딕셔너리 자료구조 할당하여 disjoint-set의 원소 수를 관리해야 함
• union(s1, s2)은 s1, s2를 대표 노드로 하는 모든 노드를 합치지 않는다.
  • s1, s2 노드에 한해서만 부모 노드를 합쳐준다
  • 즉, s2를 가리키고 있던(부모 노드로 하던) 노드의 부모 노드 값을 바꾸지 않는다.
    • 해당 노드의 부모 노드 값을 바꾸려면 find(해당노드) 해줘야 함
• 빠르게 집합의 원소 수 관리하기 위해 count를 사용한다.

코드

from sys import stdin
input = stdin.readline
T = int(input().rstrip())

def find(username):
    if username in disjoint_set:
        if disjoint_set[username] == username:
            return username
        else:
            disjoint_set[username] = find(disjoint_set[username])
            return disjoint_set[username]
    else:
        disjoint_set[username] = username
        cnt[username] = 1
        return username

def union(user1, user2):
    user1 = find(user1)
    user2 = find(user2)

    if user1 != user2: # 다른 집합에 있다
        disjoint_set[user2] = user1
        cnt[user1] += cnt[user2]

for _ in range(T):
    F = int(input().rstrip())
    disjoint_set = dict() # key : 사용자 - value : 부모노드
    cnt = dict() # 사용자 친구의 수
    for __ in range(F):
        user1, user2 = input().rstrip().split()
        union(user1, user2)
        print(cnt[find(user1)])

배운점

• disjoint-set에서 각 집합의 원소 수 관리하려면 따로 딕셔너리 지정하는게 효율적
  • union() 시에 원소 수 합쳐준다.