[알고리즘] 백준 4195번 : 친구 네트워크

백준 4195번 : 친구 네트워크 (문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 해싱, 최소 스패닝 트리
• 난이도 : 중

소스코드

import sys

t = int(sys.stdin.readline())

def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)

    parent[root2] = root1
    number[root1] += number[root2]

for _ in range(t):
    f = int(sys.stdin.readline())
    number = dict()
    parent = dict()
    for i in range(f):
        node1, node2 = sys.stdin.readline().split()
        if node1 not in parent:
            parent[node1] = node1
            number[node1] = 1
        if node2 not in parent:
            parent[node2] = node2
            number[node2] = 1

        if find(node1) != find(node2):
            union(node1, node2)

        print(number[parent[node1]])

설명

1. 딕셔너리 자료구조와 union-find 알고리즘을 사용하면 쉽게 풀 수 있다.
2. 딕셔너리 2개 필요 : parent(각 노드의 부모 노드를 저장), number(각 노드별로 몇 개의 노드와 연결되어 있는지 그 개수를 저장. 자기자신 포함) / 초기값으로 각각 자기 자신, 1을 갖는다.
3. find함수 : path-compression기법을 통해, find함수를 한 번 거친 노드는 parent딕셔너리에 자신의 '루트 노드'가 저장된다.
4. union함수 : for문 안의 for문에서 3번째 if문의 조건, 즉, node1과 node2의 '루트 노드'가 상이한 경우에만 호출되는 함수로, union함수가 실행되면 node2의 루트노드인 root2는 부모로 node1의 루트노드인 root1을 가지게 된다. 즉, parent[root2] = root1이 된다. 그리고 root1과 연결된 노드의 개수에 root2에 연결된 노드의 개수를 더해준다.
5. 반복문이 실행 될 때마다 print함수로 node1의 루트노드에 연결된 노드의 개수를 출력해주면 된다.
6. (참고) 4번에서 parent[root1] = root2로 작성해줘도 상관없다. 당연한 이야기지만, 그 이후의 과정도 전부 root1, root2를 바꿔서 작성해줘야 한다.