[BOJ][Python]1717 풀이

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

1717번: 집합의 표현

import sys
ssr = sys.stdin.readline
sys.setrecursionlimit(1000000)

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)
    if root1 != root2:
        if rank[root1] < rank[root2]:
            uf[root1] = root2
        elif rank[root1] == rank[root2]:
            uf[root1] = root2
            rank[root1] += 1
        else:
            uf[root2] = root1
    return

def find(node):
    if uf[node] == node:
        return node
    else:
        uf[node] = find(uf[node])
        return uf[node]
    
n, m = map(int, ssr().split())
uf = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]
for _ in range(m):
    query, node1, node2 = map(int, ssr().split())
    if query == 0:
        union(node1, node2)
    else:
        if find(node1) == find(node2):
            print('yes')
        else:
            print('no')

사실 풀이라고 하기는 좀 그렇습니다. 아직 개념적으로만 유니온 파인드를 이해하고 있는 정도고 몸에 체화가 된 느낌은 아니에요. 1043번에 적용하기 위해서 좀 찾아보긴 했지만 아직 코드 작성 연습이 필요할 것 같아서 일단 유니온파인드 문제를 하나 풀어봤습니다.

 

코드도 크게 설명드릴만한 부분은 없고 그냥 유니온 파인드를 검색해서 어떤식으로 작동하는지를 읽고 그걸 코드로 옮긴게 다입니다. 유니온-파인드(Union-Find) 알고리즘은 분리 집합(Disjoint Set) 자료구조(서로소 집합이라고도 부릅니다)를 탐색할 때 용이한 그래프 탐색 알고리즘의 일종입니다. 기존의 DFS/BFS와 같은 그래프 탐색 알고리즘은 각각의 연결유무를 탐색하는 것이 용이했다면 유니온 파인드는 같은 그룹에 있는지를 판단하는 것이 강점인 알고리즘이라고 할 수 있겠습니다. 연결 행렬이나 연결 리스트를 통해 각 노드와 직접 연결된 노드가 무엇인지를 판단하는 것이 쉬운게 DFS/BFS 였다면 해당 노드가 속해있는 트리의 root 노드가 무엇인지를 저장해서 같은 트리인지 판단하는게(트리 자료구조는 하나의 root 노드를 갖고 같은 트리에 존재한다면 root 노드가 동일한 것을 이용한 것입니다) 쉬운 알고리즘이 유니온 파인드라는 말입니다. 제가 공부하는데에 도움이 되었던 블로그를 첨부합니다. 유니온 파인드가 좀 더 궁금하신 분은 해당 글을 읽어보시는 것을 추천합니다. https://4legs-study.tistory.com/94

 

그래서 코드를 구현해보면 먼저 서로 다른 집합일 때 해당 집합을 합치는 Union 과정과 주어진 노드의 뿌리 노드를 확인하는 Find 과정으로 이루어집니다(그래서 유니온-파인드입니다). 위의 링크에서 유니온 파인드에 대해서 읽어보셨다면 정말 말그대로 유니온 파인드를 그대로 구현하면 되는 문제라 딱히 어렵지는 않습니다.