[BOJ] #4195 - 친구 네트워크

4195번: 친구 네트워크

 

** 문제 유형

• 해시, 집합, 네트워크

 

** 풀이

1. 해시를 활용한 Union-Find(합집합 찾기) 알고리즘을 이용해 문제 해결
2. 파이썬 - dictionary 자료형을 해시처럼 사용

 

+) 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):
    f = int(input())
    parent = dict()
    number = dict()

    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)])