백준 4195번:친구 네트워크

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

<코드>

from sys import stdin

input = stdin.readline

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


def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a
        number[a] += number[b]
    print(number[a])


for _ in range(int(input())):
    num = int(input())
    parent, number = {}, {}
    for i in range(num):
        a, b = input().split()
        if a not in parent:
            parent[a] = a
            number[a] = 1
        if b not in parent:
            parent[b] =b
            number[b] = 1
        union(a, b)

 

 

<풀이과정>

해시 알고리즘이라 딕셔너리에 [친구]: [속한 친구 리스트] 이런식으로 저장을 해줘야된다고 생각을 하였다.
그런데, 메모리도 그렇고, 코드도 복잡해지고, 구현이 잘 안되어서 구글링을 해봤더니 union-find 알고리즘을 써야된다고 하였다
우선 유니온-파인드 알고리즘이란 서로소 집합(disjoint set)을 효율적으로 다루기 위한 자료구조와 관련된 알고리즘이다.
간단히 말하자면 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다.

우선 입력을 받을때 친구 1 이름과 친구 2의 이름을 딕셔너리에 넣어준다음에 count의 수를 세줘야 하니 자기와 연결된 노드들의 갯수를 1로 먼저 초기화 해준다. ->본인은 본인과 연결이 되기때문!

그리고 유니온 연산을 해주면 친구1과 친구 2의 뿌리를 구해준다음, 뿌리가 다르므로 친구2의 뿌리를 친구 1로 바꿔주면 둘이 합쳐지게 된다.

이때 친구2는 1명으로 세어지니, 친구1에 1명을 더해주면 친구는 2명이 생기는 것이다.