분류

  • 그래프 알고리즘 (무향 그래프)
  • 사이클 판단

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def init_parent(parent, n):
    for i in range(n):
        parent[i] = i

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

    return x

def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

설명

서로소 집합 (Disjoint Sets)

공통 원소가 없는 두 집합을 의미한다.

서로소 집합을 표현하는 알고리즘

union - 두 노드의 부모를 일치시킨다. (= 병합)

find - 두 노드의 부모가 같은지 검사한다. (= 같은 집합인가?)

병합 절차

  1. Union (합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
    1. A와 B의 루트 노드 A’, B’를 각각 찾는다.
    2. A’과 B’중 작은 인덱스로 연결해준다.
  2. 모든 Union (합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

무향 그래프에서 사이클 판단

비방향성 그래프에서 어떤 두 개의 노드가 서로 같은 집합에 속한다는 뜻은 사이클이 존재한다는 의미이다.

따라서, 비방향성 그래프의 사이클 판단 여부에 사용된다.

참고 레퍼런스

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)