백준 4195번 문제(친구의 네트워크) with python

# 친구의 네트워크
# union-find algorithm을 이용한 풀이
# union 함수를 통해 parent 노드를 만들어준다
# fine 함수를 통해 parent 노드를 찾아준다
# test 케이스에서는 parent인지 아닌지를 확인해준다

def find(x):
    if parent[x]==x:
        return x
    else: # parent가 자기 자신이 아닐 경우
        root_x=find(parent[x]) # x의 root값
        parent[x]=root_x # x의 parent를 x의 root값으로 할당한다
        return parent[x] # x의 parent값을 반환해준다

# x와 y의 parent값이 같을 경우 넘긴다
# x와 y의 parent값이 다를 경우 y의 root 노드로 x값을 지정해준다
def union(x,y):
    root_x=find(x) # x의 root 노드를 찾아준다
    root_y=find(y) # y의 root 노드를 찾아준다

    if root_x!=root_y: 
        parent[root_y]=root_x
        number[root_x]+=number[root_y] #number[root_x] 값을 key로 하여 number[root_y]가 value가 되게 한다

test_cases=int(input())   
    

for i in range(test_cases):
    parent=dict()
    number=dict()
    a=int(input())
    for j in range(a):
        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)]) # 이렇게 하면 fine(x)를 통해 root를 찾고 root에 해당하는 number 배열에 관한
        # 노드들이 쭉 딸려나오게 된다

이 문제는 union-find라는 알고리즘을 알고 있다면 쉽게 풀 수도 있지만 모른다면 상당히 어렵게 풀어야 하는 문제이다

나는 해당 몰라서 매우 많이 헤맨 뒤 구글링을 통해 union-find의 개념에 대해 알게 되었다

union-find는 기본적으로 union을 통하여 parent-child 관계를 형성해주고 find를 통해 parent-child 관계가 형성된 것을 return 받는 형식으로 사용하게 된다

 

위 코드를 보게 되면 알겠지만 이 개념에 앞서 사전형에 대하여 명확한 개념을 알고 있어야 한다

dict()형으로 parent, number를 지정했기 때문에 key,value 쌍으로 묶이게 되고, 결과값의 경우는 chain 형식으로 특정 parent가 key로 child 리스트가 value값으로 들어가게 된다.

결과적으로 dict() 형태로 선언한 numbers 배열에서 parent가 아닌 마지막 child 노드의 value는 1이다.

이 child 노드의 parent가 존재할 때마다 numbers배열은 1씩 더해진다.