[백준 4195번] 친구 네트워크

📌 문제

👊 백준 4195번 - 친구 네트워크

📌 개념

hash union-find

• union(x, y) : 합하기
  - x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산
• find(x) : 찾기
  - x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산
  

✅ 문제 해결

• parent는 각 학생들의 최상위 부모를 담은 dict이다. 즉 parent dict의 key는 각 학생들의 이름, value는 각 학생들의 최상위 부모이다.
• number은 각 학생 노드가 가지고 있는 하위 노드의 개수를 담은 dict이다. 즉 number dict의 key는 각 학생들의 이름, value는 각 학생 노드의 하위 노드의 개수이다.
• union(f1, f2) : f2가 f1을 가리키도록 합치는 연산이다. 즉 f2는 f1에 연결된 하위 노드이다.
• find(item) : item의 root(최상위 부모)를 찾아서 반환하는 함수이다.

예제로 이해하기

• 1. Fred Barney / Barney Betty / Betty Wilma를 입력하는 경우
     
• 2. Fred Barney, Betty Wilma, Barney Betty를 입력하는 경우
     

Code

• find(item) : 해당 원소의 최종 부모를 찾음

def find(item):
    if item == parent[item]:
        return item
    else:
        p = find(parent[item])
        parent[item] = p
        return parent[item]

• union(f1, f2) : 최종 부모를 고려하여 두 개의 노드를 연결함

def union(f1, f2):  # f2의 부모는 f1
    f1 = find(f1)
    f2 = find(f2)
    if f1 != f2:  # 이거 안해주면 틀리네...
        parent[f2] = f1
        number[f1] += number[f2]

• 실행 코드

test_case = int(input())
for _ in range(test_case):
    parent = {}  # parent의 key는 이름, value는 최상위 부모
    number = {}  # number의 key는 이름, value는 하위 노드 개수
    f = int(input())
    for _ in range(f):
        f1, f2 = input().split(" ")

        if f1 not in parent: # 처음 나왔을 경우 새롭게 추가해줌
            parent[f1] = f1
            number[f1] = 1

        if f2 not in parent: # 처음 나왔을 경우 새롭게 추가해줌
            parent[f2] = f2
            number[f2] = 1

        union(f1, f2)
        print(number[find(f1)]) # 최상위 부모에 연결된 노드 개수를 출력한다.

• 다시 풀어보자 쪼금 어렵다😪