[백준 4195 파이썬] 친구 네트워크 (골드 2, 유니온 파인드)

알고리즘 유형 : 유니온 파인드
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/4195

소스 코드(파이썬)

import sys
from collections import deque
input = sys.stdin.readline

# 그래프를 딕셔너리로 표현
# 키는 유저명, 값은 음수인 경우는, 루트 노드임을 의미하면서, 절댓값이
# 자신을 포함한 트리의 크기를 의미함. 양수인 경우는 부모 노드명을 의미
def find(user):
    if graph.get(user) == None:
        graph[user] = -1
        return user
    
    if type(graph.get(user)) == int and graph.get(user) < 0:
        return user
        
    graph[user] = find(graph[user])
    return graph[user]

def union(user1, user2):
    root1 = find(user1)
    root2 = find(user2)
    
    if root1 == root2:
        return
    
    # 루트 노드의 graph값의 절댓값이 트리의 크기를 나타내므로,
    # union할 때 새로운 루트 노드에 합쳐지는 트리의 크기 값을
    # 더 빼주면 됨. 이 때 합치는 기준은 그냥 적당히 트리의
    # 크기가 작은 것을 큰 것쪽으로 합치는걸로 했음
    if graph[root1] < graph[root2]:
        graph[root1] += graph[root2]
        graph[root2] = root1
    else:
        graph[root2] += graph[root1]
        graph[root1] = root2
        
    return

for _ in range(int(input())):
    F = int(input())
    graph = {}
    
    for i in range(F):
        user1, user2 = input().split()
        
        union(user1, user2)
        
        # 루트 노드의 절댓값 출력
        root = find(user1)
        print(-graph[root])

풀이 요약

1. weighted union find로 쉽게 풀 수 있다.

2. 이번 문제는 노드에 순서대로 번호를 붙여지는게 아닌, 노드가 고유한 이름을 가질 때 어떻게 그래프로 나타낼 것인지를 생각해봐야한다.

   특정 유저를 인덱싱하여 부모 노드를 확인해야하는데 특정 유저의 네이밍이 문자열이다. 딱 봐도 딕셔너리가 적당해보인다.

   키-값이 유저명-(부모노드or음수이면서절댓값이트리의크기인값)

   을 의미한다.

3. 우선 find 함수를 먼저 구현하자.

   유저명으로 인덱싱을 했을 때 값이 존재하지 않는 경우와 값이 음수인 경우에는, 본인이 루트 노드인 경우이다. 따라서 전자의 경우에는 딕셔너리에 -1로 등록해주고, 두 경우 공통적으로 유저명을 그대로 리턴해준다.

   그 외의 경우는 값에 부모 노드의 유저명이 들어있는 경우이므로, 부모 노드의 루트 노드를 자신의 루트 노드로 삼고 그 것을 리턴한다.

4. union 함수를 작성하자. 입력으로 들어온 두 노드의 루트 노드를 find 함수로 찾고, 그 둘이 같다면 이미 같은 그래프 상에 있으므로 종료.

   그 외의 경우에는 합쳐준다. 합칠 때, 합침 당하는 쪽의 트리의 크기(graph 리스트 원소 값의 절댓값)를 합침 기준 트리의 트리 크기에 더해준다(음수 + 음수 = 더 작은 음수). 트리의 크기가 더 작은 것을 큰 것쪽으로 합치도록 조건문을 짰는데 큰 의미는 없다.

5. 이제 친구 네트워크 관계 쌍을 입력받을때마다, union해주고, 둘 중 하나의 루트 노드를 find로 찾아서 그 루트 노드의 graph값의 절댓값을 출력해준다.

6. 물론 이렇게 weighted union find말고, 그냥 유니온 파인드를 적용하고 따로 트리의 크기를 나타내는 딕셔너리를 만들어서 활용해도 맞는 풀이이다.

배운 점, 어려웠던 점

• weighted union find 활용력을 기를 수 있어 유익한 문제였다.