❗️[Baekjoon] 4195. 친구 네트워크

# Problem

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다. 출력 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

새로 들어온 관계를 포함한 관계의 개수

 

ex2) 

Fred - Barney  2

Bettty-Wilma  2

Fred - Barney - Betty - Wilma   4

 

# Solution 1 - Union-Find 알고리즘 활용 (합집합 찾기)

def find(x): # 루트 노드 찾기
    if x == parent[x]:
        return x
    else:
        p = find(parent[x]) 
        parent[x] = p 
        return parent[x]

def union(x, y): 
    x = find(x) 
    y = find(y)
    if x != y:  # 루트 노드가 다르다면 하나로 합치기
        parent[y] = x
        number[x] += number[y]
test_case = int(input())

for _ in range(test_case): 
    parent = dict()
    number = dict()
    f = int(input())
    for _ in range(f):
        x, y = input().split(' ')
        if x not in parent: # 새로운 노드일 경우
            parent[x] = x
            number[x] = 1
        if y not in parent: # 새로운 노드일 경우 
            parent[y] = y 
            number[y] = 1
        union(x, y) # 두 친구는 연결되어 있으므로 하나로 연결
        print(number[find(x)])

 

---

# Union - Find 알고리즘 ( 합집합 찾기 )

원소들의 연결 여부를 확인하는 알고리즘

 

부모 루트를 찾아주는 find 함수를 정의 

두 루트 노드를 비교해서 union by rank 기법으로 합쳐주는 union 함수 정의

 

# union- by - rank 기법

각 트리의 높이 (rank)를 기억하고 union시 높이가 다르면 작은 트리를 큰 트리에 붙임 

rank가 동일할 경우 한쪽의 rank를 하나 올려주고 다른 트리를 붙임