벨만-포드 알고리즘(Bellman-Ford algorithm)은 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 특징 중 하나는 엣지의 가중치가 음수여도 활용이 가능하다는 점이며, 이러한 음수 사이클의 존재 여부를 판별하는 것이 벨만-포드 알고리즘의 중요한 것 중 하나 입니다. 벨만-포드 알고리즘의 구체적인 작동 원리는 아래와 같이 구현할 수 있습니다.

1단계 : 초기화

벨만-포드 알고리즘은 엣지를 중심으로 동작하기 때문에 엣지 리스트를 구현합니다. 이전 다른 그래프 경우와 유사하게, 거리 리스트에 대해서는 출발 노드는 0, 나머지 노드는 무한대로 초기화도 수행합니다.

graph = [] # 에지 리스트
for _ in range(num_edge):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

D = [float('inf')] * n  # 노드의 개수
D[start] = 0

2단계 : 거리 리스트 업데이트

모든 에지를 확인해 총 (n-1)번 거리 리스트를 업데이트합니다. (D[e] = D[s] + w) 업데이트를 수행하기 위한 AND 조건은 다음과 같습니다. 

• D[s] != inf
• D[e] > D[s] + w

for _ in range(n-1):
    for s, e, w in graph:
        if D[s] != float('inf') and D[e] > D[s] + w:
            D[e] = D[s] + w

3단계 : 음수 사이클 탐지 

에지 리스트에 있는 모든 에지에 대해서 위에서 언급한 조건을 만족하는 경우에는 음수 사이클이 존재하는 것을 알 수 있습니다. 

    for s, e, w in graph:
        if D[s] != float('inf') and D[e] > D[s] + w:
            return None
    return D

최종 코드

위에서 설명한 단계에 따른 최종 코드는 아래와 같이 구현할 수 있습니다.

graph = []
for _ in range(num_edge):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

def bellman_ford(start, graph):
    D = [float('inf')] * n     # 노드의 개수
    D[start] = 0

    for _ in range(n-1):
        for s, e, w in graph:
            if D[s] != float('inf') and D[e] > D[s] + w:
                D[e] = D[s] + w

    for s, e, w in graph:
        if D[s] != float('inf') and D[e] > D[s] + w:
            return None
    return D

참고자료

[1] 위키피디아 : 벨먼 - 포드 알고리즘

[2] Do it! 알고리즘 코딩 테스트 : 파이썬 편

플로이드-워셜(Floyd-Warshall) 알고리즘은 특정 노드가 아닌 모든 노드에서 최단 경로를 찾을 수 있는 알고리즘 입니다. 그래프의 모든 노드에서 다른 노드까지 최단 경로를 계산하는 것으로 (특정 시점에 국한된 것이 아닌) 각 노드에서 다른 노드까지 최단 경로의 행렬을 반환합니다.

3개의 for문으로 비교적 쉽게 구할 수 있지만, 그만큼 많은 연산을 요구합니다. 코딩 테스트 문제에서 만약 나온다고 하면, 비교적 노드 범위 개수가 적게 주어질 경우 이 알고리즘을 적용해보는 것도 방법이 될 듯 합니다. 

1 단계 : 초기화

D[s][e]는 노드 s에서 e까지 가는 최단 거리를 저장하는 거리 리스트 입니다. 먼저 이 리스트를 출발 ~ 도착 지점이 같은 경우 (s =e) 0, 다른 칸을 무한대의 값으로 초기화 합니다. 

V = len(graph) # 노드 개수 
D = [[float('inf') * (V+1) for _ in range(V+1)]]

# 자기 자신에게 가는 거리 = 0
for i in range(1, V+1): 
    D[i][i] = 0

2 단계 : 그래프 데이터 저장

출발 노드[s]와 도착 노드[e], 가중치 w라고 했을 때 D[s][e] = w 로 저장을 진행합니다. 코드에서는 graph를 따로 입력 받은 것을 가정하기 때문에 아래와 같이 코드를 입력할 수 있습니다. 

# 그래프 데이터 저장
for i in range(V):
    for j in range(V):
        D[i][j] = graph[i][j]

3 단계 : 점화식 

플로이드-워셜 알고리즘은 아래 점화식을 진행하면 됩니다. 

위 점화식은 아래와 같이 구현 가능합니다. 

# 점화식에 따라 업데이트
for k in range(1, V+1):
    for s in range(1, V+1):
        for e in range(1, V+1):
            if D[s][e] > (D[s][k] + D[k][e]):
                D[s][e] = (D[s][k] + D[k][e])

최종 코드

위 단계를 모두 종합하면 아래와 같이 요약될 수 있습니다. 아래 코드에서 반환하는 D 행렬은 출발 ~ 도착 노드에서 최단 거리를 구할 수 있습니다. 예를 들어, 1부터 5까지 가는 최단 거리는 D[1][5]를 통해 구할 수 있습니다.

def floyd_warshall(graph):
    V = len(graph) # 노드 개수 
    D = [[float('inf') * (V+1) for _ in range(V+1)]]
    
    for i in range(1, V+1): 
        D[i][i] = 0

    for i in range(V):
        for j in range(V):
            D[i][j] = graph[i][j]
    
    for k in range(1, V+1):
        for s in range(1, V+1):
            for e in range(1, V+1):
                if D[s][e] > (D[s][k] + D[k][e]):
                    D[s][e] = (D[s][k] + D[k][e])

    return D

다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 노드 간 최단 경로를 찾는 알고리즘 입니다. 이러한 특성을 이용해서 네트워크 경로 탐색, 그래프 기반 최적화, GPS 등 문제에서 사용이 가능합니다. 

알고리즘 동작 원리

다익스트라 알고리즘은 다음 5단계로 구성할 수 있습니다. 

1. 주어진 그래프를 인접 리스트를 구현 합니다.
2. 출발 노드를 설정(0)하고, 이외의 다른 노드들은 무한대로 초기화합니다.
3. 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 선택합니다. 선택된 노드는 방문 처리 합니다. (맨 처음에는 출발 노드에서 시작합니다)
4. 방문 처리한 노드를 지나서 다른 노드를 탐색하면서 더 짧은 경로가 있으면 다른 노드를 업데이트 합니다.
5. 3~4 과정을 모든 노드를 방문할 때까지 반복합니다.  

1단계 : 인접 리스트 구현

인접 리스트는 다른 그래프 문제에서도 많이 사용하는만큼 동일하게 구현하면 됩니다. 다만, 다익스트라의 경우 엣지의 가중치가 존재하므로 3개의 입력값을 받는다는 사실만 기억하면 됩니다. 알고리즘 테스트에 대비하기 위한 형태로 구현하면 다음과 같습니다.

graph = [[] for _ in range(num_node)]
for _ in range(num_edge):
    s, e, w = map(int, input().split())
    graph[s].append((e, w))

2단계 : 초기화

다음으로는 거리에 대한 초기화를 진행합니다. 출발 노드는 0, 이외의 노드는 무한으로 초기화합니다. 이 때 시작점도 (거리, 노드) 형태로 같이 설정합니다.

distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)] # 시작점 설정

3단계 :  노드 방문 여부 체크 

먼저 방문하지 않은 노드를 찾습니다. 다익스트라 알고리즘에서는 현재 노드에서 거리가 거리 리스트에 있는 값보다 크면, 이미 처리된 노드임을 알 수 있습니다. (왜냐하면 그전까지는 무한의 값이기 때문에) 이미 방문한 노드이면 continue로 다음 노드를 꺼내옵니다. 

current_distance, current_node = heapq.heappop(pq)
        
# 이미 처리된 노드는 무시
if current_distance > distances[current_node]:
    continue

4단계 : 최단 경로 업데이트 

선택된 노드에서 다른 노드에 연결된 경로를 확인하면서, 더 짧은 경로가 있으면 해당 경로로 업데이트 합니다. 더 짧은지 여부는 (선택한 노드의 거리 리스트 값 + 에지 가중치)와 (연결된 노드의 거리 리스트 값)을 비교해서 업데이트를 수행 합니다. 

# 이웃 노드 확인
for neighbor, weight in graph[current_node].items():
    distance = current_distance + weight
    # 더 짧은 경로 비교 
    if distance < distances[neighbor]:
        distances[neighbor] = distance # 업데이트 
        heapq.heappush(pq, (distance, neighbor))

전체 코드

앞 과정 3~4단계를 반복하면서 모든 노드에 대해 처리될 때까지 수행합니다. 이는 우선순위 큐가 빌 때까지 수행되는 while 문으로 구현 가능합니다. 위 단계까지 포함하여 구현된 코드는 아래와 같습니다.

import heapq

graph = [[] for _ in range(num_node)]
for _ in range(num_edge):
    s, e, w = map(int, input().split())
    graph[s].append((e, w))

def dijkstra(graph, start): 
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)] 
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

참고자료

[1] "Do it! 알고리즘 코딩 테스트 파이썬편" 

[2] 위키피디아 : 데이크스트라 알고리즘

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 발견한 소수(prime number)를 찾는 방법입니다. 수학시간은 아니므로 소수냐 합성수냐에 대한 정의 설명은 생략하고, 어떤 방식으로 동작하는지 살펴보겠습니다.

1. 소수를 찾고자 하는 구간의 모든 수를 나열합니다.

2. 어느 한 소수의 배수를 모두 지웁니다.

3. 남아있는 수 가운데 다음 소수를 찾습니다. 

4. 2-3 과정을 반복합니다.

여기서 2가지 포인트가 있습니다. 먼저, 위 과정에서 2단계의 최초 시작은 2부터 합니다. (왜냐하면 1은 소수도 합성수도 아닌 수이기 때문입니다) 그다음은 3, 5, 7.... 순으로 커지게 됩니다. 

두번째는 최대 약수는 어느 숫자의 제곱근을 넘을 수 없다는 사실입니다. 정수론 시간이 아니므로 엄밀한 증명은 넘어가더라도, 제곱근 값을 넘어가게 된다면 나머지 다른 약수는 제곱근보다 작은 숫자일 것입니다. 작은 숫자는 이미 카운트가 됐을 것이므로, 따라서 제곱근을 넘을 수 없는 것으로 셀 수 있을 것입니다.

이를 코드로 구현하면 다음과 같습니다.

# 에라토스테네스의 체
def eratos(n):
    sieve = [True] * n
    gcd = int(n ** 0.5)

    for i in range(2,  gcd+1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False   
    return [i for i in range(2, n) if sieve[i] == True]

print(eratos(20))

아래 사진을 보면, 잘 동작하는 것을 확인할 수 있습니다.

참고:

1. Wikipedia, "에라토스테네스의 체" 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

위키피디아를 참고하면 다이나믹 프로그래밍, 다른 말로 동적계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 것을 의미합니다. 한편, 알고리즘 스터디를 위해 참고하는 블로그(안경잡이 개발자)에서는 '하나의 문제를 단 한 번만 풀도록 하는 알고리즘'이라고 정의하고 있습니다.

일반적으로 분할 정복 기법은 동일한 문제를 다시 풀기 때문에 비효율적입니다. 그러나 다이나믹 프로그래밍은 하나의 문제를 한 번만 풀도록 하기 때문에 비효율적인 알고리즘을 개선시킬 수 있습니다. 구현에 대한 사례로 피보나치 수열을 활용하겠습니다. 중/고등학교 수학시간에서 배운 것처럼, 피보나치 수열은 어느 숫자를 구하기 위해서 그 앞과 앞앞 자리의 숫자를 더하면서 구해가는 수열입니다. 이를 식으로 나타내보면 다음과 같습니다. 

a(n)  = a(n-1) + a(n-2)

여기서 a(n)을 계산하기 위해서는 a(n-1)과 a(n-2) 값이 필요한데, 이를 해결하기 위해서는 해당 값들을 특정 메모리에 저장해서 나중에 필요할 때 꺼내쓰는 방식이 필요합니다. 이를 메모이제이션(memoization)이라고 하며, 동일한 연산을 반복할 때 새로 연산이 필요없이 꺼내쓰기만 해서 불필요한 행위를 줄이는 것입니다.

(쉽게 말해, 옆에 메모해두고 필요할때마다 보고 사용하는 것입니다)

이를 구현하는 것은 그렇게 어렵지 않습니다. 

# Fibonacci

d = [0] * 100

def fibo(x):
    if (x == 1):
        return 1
    if (x == 2):
        return 1
    if (d[x] != 0):
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(30))

피보나치수열로 30번이면 꽤 많은 연산을 수행했는데도, 제법 빠르게 나오는 것을 확인할 수 있습니다. 

참고:

1. Wikipedia, 동적계획법(Dynamic Programming)

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

2. 안경잡이 개발자, "20. 다이나믹 프로그래밍 (Dynamic Programming)"

https://blog.naver.com/ndb796/221233570962

이전 글에서 이진트리에 대해서 알아봤습니다. 이진트리 자료구조에 대한 사항은 아래 글을 참고하시기 바랍니다. 

https://seanpark11.tistory.com/82

이러한 트리 구조에서 각가의 노드를 정확히 한번만 방문하는 것을 체계화한 것이 트리순회(Tree Traveral, 줄여서 순회)입니다. 여기서 구현해볼 순회의 방법은 3가지 입니다 : 전위순회(Preorder Traversal), 중위순회(Inorder Traversal), 후위순회(Postorder Traversal). 사실은 더 많은 순회에 대한 내용들이 있지만, 편의상 이 세가지 내용만 다루고자 합니다.

먼저 전위순회는 다음과 같은 순서입니다.

1. 노드를 방문
2. 왼쪽 자식을 전위순회
3. 오른쪽 자식을 전위순회

앞서 언급한 트리 예시를 사용하면, 방문순서는 1-2-4-5-3-6-7 입니다. 이를 코드로 구현하면 다음과 같습니다.

class BinaryTree():
    def __init__(self):
        self.root = None
        
    # 전위 순회
    def preorder(self, n):
        if n != None:
            print(n.item, ' ', end='')
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)


# 전위 순회 출력
print("전위 순회 : ")
bt.preorder(bt.root)
print("\n")

다음은 중위순회 입니다.

1. 왼쪽 자식을 중위 순회
2. 노드를 방문
3. 오른쪽 자식을 중위 순회

동일한 트리 예시를 사용하면, 중위순회의 방문순서는 2-4-5-1-3-6-7 입니다. 이를 코드로 구현하면 다음과 같습니다.

class BinaryTree():
    def __init__(self):
        self.root = None

    # 중위 순회
    def inorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left)
            print(n.item, ' ', end='')
            if n.right:
                self.preorder(n.right)
                
# 중위 순회 출력
print("중위 순회 : ")
bt.inorder(bt.root)
print("\n")

마지막은 후위순회는 다음과 같은 순서로 방문합니다.

1. 왼쪽 자식을 후위순회
2. 오른쪽 자식을 후위순회
3. 노드를 방문

마찬가지로 예시를 살펴보면, 후위순회의 방문순서는 2-4-5-3-6-7-1 입니다. 이를 코드로 구현하면 아래와 같습니다. 

class BinaryTree():
    def __init__(self):
        self.root = None

    # 후위 순회
    def postorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)
            print(n.item, ' ', end='')

# 후위 순회 출력
print("후위 순회 : ")
bt.postorder(bt.root)
print("\n")

참고 내용

1. 안경잡이 개발자, "19. 이진 트리의 구현과 순회(Traversal)",

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221233560789&navType=by 

2. Wikipedia, "트리 순회",

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

이진트리(Binary Tree)는 각가의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조 입니다. 왼쪽에 있는 자식노드를 '왼쪽 자식 노드', 오른쪽에 있는 자식노드를 '오른쪽 자식 노드'로 구분합니다. (약간 말장난같지만, 이 둘은 분명히 다른 노드이기 때문에 다른 용어가 필요합니다) 엄밀한 의미의 정의는 아니지만 이런 형태의 정의도 이해하기 충분하니, 다음은 몇 가지 용어로 넘어가겠습니다.

노드(Node) : 데이터를 저장하는 기본 요소

부모 노드(Parent Node) : 어느 노드를 자식으로 갖는 노드

자식 노드(Child Node) : 어느 노드를 부모로 갖는 노드

형제 노드(Sibling Node) : 부모가 같은 노드

차수(Degree) : 자식의 수

루트 노드(Root Node) : 트리 맨 위에 있는 노드

깊이(Depth) : 루트 노드에서 어느 노드까지 가는 경로의 길이 

레벨(Level) : 루트 노드에서 어느 노드까지 가는 경로의 길이 +1

다음은 실제 사례를 보면서 파이썬으로 구현해보겠습니다. 아래 그림과 같은 이진트리를 생각해보겠습니다. 

1은 루트 노드이고, 왼쪽 자식 노드는 2 오른쪽 자식 노드는 3을 가진 것을 알 수 있습니다. 그 아래로 차례로 2는 4, 5를 3은 6, 7을 각각 왼쪽 자식 노드, 오른쪽 자식 노드로 갖습니다. 이를 파이썬으로 구현하면 다음과 같습니다.

class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

class BinaryTree():
    def __init__(self):
        self.root = None
    
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)

bt = BinaryTree()
bt.root = n1
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

참고자료

1. Wikipedia, 이진트리(Binary Tree) 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

2. 

크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 이는 '최소 비용 신장 트리'를 찾는다고 표현하기도 합니다. 사실 구글링을 조금만 해도 설명이 잘된 글이 많아 남들처럼 세세하게 그림을 그리면서 설명하지는 않고, 제가 이해한데로 종합하고자 합니다. 

우선, 알고리즘을 설명하기에 앞서 몇 가지 단어의 개념을 짚고 넘어가고자 합니다. 

간선: 노드끼리 연결한 그래프에서 선에 해당

사이클: 노드끼리 연결한 그래프가 서로 연결되어 루프를 형성하는 경우

여기서 최소 비용 신장 트리에서는 사이클이 발생하면 안됩니다. 간단히 생각하더라도, 사이클이 있으면 거리가 멀어지게 되기 때문에 최소 비용이 아니기 때문입니다. 크루스칼 알고리즘의 순서는 아래처럼 흘러갑니다. 

1. 모든 간선들을 거리를 기준으로 오름차순 정렬 수행

2. 정렬 순서에 맞게 그래프에 포함

3. 포함시키기 전 사이클 테이블을 확인

4. 사이클을 형성하는 경우 간선을 포함하지 않음

- 여기서 사이클 형성 여부를 체크할 때는 Union-Find 알고리즘을 적용

import sys

# Union-Find 와 동일
N = int(sys.stdin.readline().rstrip()) # 노드 수
e = int(sys.stdin.readline().rstrip())
parent = [0] * (N+1) # 부모 행 초기화
# 부모 행 자기자신으로 설정
for n in range(1, N+1):
    parent[n] = n

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

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] =a
    else:
        parent[a] = b

# 간선 정보 
edges = []
total_cost = 0

for _ in range(e):
    a, b, cost = map(int, sys.stdin.readline().split())
    edges.append((cost, a, b))
# 거리 기준으로 오름차순 정렬
edges.sort()

for i in range(e):
    cost, a, b = edges[i]
    if (find(parent, a) != find(parent, b)):
        union(parent, a, b)
        total_cost += cost

print(total_cost)

입력값을 아래 링크와 동일하게 사진과 같이 넣으면 total_cost가 123으로 동일하게 나오는 것을 확인할 수 있습니다.

참고자료

1. 안경잡이 개발자, "18. 크루스칼 알고리즘(Kruskal Alogrithm)",

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221230994142&navType=by 

2. Wikipedia, https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 유니언 파인드(Union Find), 한글로 '합집합 찾기'는 그래프 알고리즘입니다. 알고리즘의 목표는 여러개의 노드에서 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 것입니다. 그 과정을 아래 예시를 통해 설명하겠습니다.

 1~8까지 있는 노드를 가정하면, 아래 표와 같이 나타낼 수 있습니다. 위 행은 노드 번호, 아래는 부모노드의 번호로 각 노드가 어떤 부모 노드에 포함되어 있는지를 나타냅니다. 연결이 없이 자기자신만 있는 경우 노드와 부모노드가 같을 것이고, 서로 다른 노드가 연결되는 경우 아래 부모노드가 바뀌게 됩니다.

 1과 2가 연결된 상태를 가정하면, 위표는 아래와 같이 바뀌게 됩니다. 여기서 우리가 세울 규칙은 '연결할 때는 더 작은 값을 부모노드'로 합니다. 여기서 연결은 합침으로도 바꿔 표현할 수 있으며, 그렇기 때문에 Union(합침)이라는 함수가 등장합니다.

 이 상태에서 2와 3을 연결하겠습니다. 위에서 세운 규칙에 따라 3과 연결된 부모노드는 2로 변경됩니다. 하지만, 1과 2가 연결된 상태에서 3도 연결한다면, 1과 3이 연결된 상태인데 이를 나타낼 필요가 있고, 재귀함수를 사용할 수 있습니다. 

 재귀함수는 3의 부모로 2를 찾고, 2의 부모로 1을 찾습니다. 아래와 같이 그림으로 표현이 가능합니다. 이런 과정을 통해 부모 노드를 확인하여 같은 집합에 속하는지 확인하는 것을 Find라고 합니다. 

 즉, Union-Find 알고리즘은 2가지 함수로 구성되며, Union이란 함수를 통해 더 작은 값을 부모노드로 하고, Find라는 함수를 통해 재귀적으로 같은 집합에 속하는지를 확인합니다. 이렇게 확인을 통해 알고리즘의 목표를 달성할 수 있습니다. 그러면 아래 소스코드를 살펴보도록 하겠습니다.

N = int(input()) # 노드 수
parent = [0] * (N+1) # 부모 행 초기화
# 부모 행 자기자신으로 설정
for n in range(1, N+1):
    parent[n] = n

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

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] =a
    else:
        parent[a] = b
        
union(parent, 1, 2)
union(parent, 2, 3)
union(parent, 3, 4)
union(parent, 5, 6)
union(parent, 6, 7)
union(parent, 7, 8)

if (find(parent, 1) == find(parent, 5)):
    print(1)
    print(parent)
else:
    print(0)
    print(parent)

노드를 위 사례처럼 8로 입력을 하고 (1,2,3,4)를 연결하고, (5,6,7,8)을 연결했습니다. 

그렇다면, 1과 5를 연결하면 어떨까요? 위 코드 중 union 블록을 아래와 같이 변경하면 결과도 달라집니다.

union(parent, 1, 2)
union(parent, 2, 3)
union(parent, 3, 4)
union(parent, 5, 6)
union(parent, 6, 7)
union(parent, 7, 8)
union(parent, 1, 5)

참고자료

1. 안경잡이 개발자, "17. Union-Find(합집합 찾기)",

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221230967614&navType=by