[Gold II] 친구 네트워크 - 4195

문제 링크

성능 요약

메모리: 61296 KB, 시간: 9092 ms

분류

자료 구조, 분리 집합, 해시를 사용한 집합과 맵

문제 설명

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

풀이

test_case = int(input())

# Find(x): 재귀적으로 함수를 호출하며, x의 Root노드를 반환
def find(x):
    if x == parents[x]:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

# Union(x,y): x와 y의 Root노드를 찾고, y의 Root노드를 x로 한다.
def union(x, y):
    x = find(x)
    y = find(y)
    
    if x != y:
        parents[y] = x
        child_num[x] += child_num[y]
    

for _ in range(test_case):
    relations = int(input())
    parents = dict()
    child_num = dict()
    
    for _ in range(relations):
        x, y = input().split()
        
        if x not in parents:
            parents[x] = x
            child_num[x] = 1
        if y not in parents:
            parents[y] = y
            child_num[y] = 1
        
        union(x, y)
        print(child_num[find(x)])

설명

• Union-Find의 개념을 알아야 한다.
  • 처음에 아이디어가 떠오르지 않아서 Union-Find를 사용하면 된다는 힌트를 얻고 아래 사이트를 통해 공부한 뒤 다시 풀이했다.
    https://twpower.github.io/115-union-find-disjoint-set
  • Union-Find란?
    • 서로소 집합(Disjoint Set) 그리고 병합 찾기 집합(Merge Find Set)이라고도 불리며, 여러 서로소 집합의 정보를 저장하고 있는 자료구조
    • 해당 문제에서는 Fred-Barney, Barney-Betty => Fred-Barney-Betty처럼 관계를 잇기 위해 부모 자식 관계를 활용할 수 있다.

• Dictionary 활용
  • parents : {자기 이름:부모} -> 부모는 union 함수를 통해 갱신된다.
  • child_num : {자기 이름:숫자} -> 상위 노드일수록 숫자에 자식의 수가 늘어남.

• 문제풀이 과정