최소 스패닝 트리 (최소 신장 트리, MST)

들어가며

때는 2024년 1월 19일, 백준의 1197번 알고리즘 문제인 최소 스패닝 트리를 풀려고 했다.

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

1197번: 최소 스패닝 트리

그런데...! 스패닝 트리가 뭔지도 모르는 나에게 이 문제를 풀기 위한 알고리즘 이름이 무려 5개가 필요했다.

 

1. 최소 스패닝 트리(Minimum Spanning Tree, MST)
2. 프림 알고리즘 (Prim's Algorithm)
3. 크루스칼 알고리즘 (Kruskal's Algorithm)
4. 우선순위 큐(Priority Queue)
5. 유니온-파인드(Union-Find) 알고리즘

 

방금 내가 본 문제는 간단해 보이지만 자그만치 5개의 CS 개념이 합쳐진 컴비네이션

 

문제를 보고 오랜 시간을 들였지만 풀지 못한다고 판단하여 풀이 중단했고, 답안을 보아도 이해가 안 되는 부분이 너무 많아 이 문제를 풀기 위한 개념 정리를 의식의 흐름대로(중요) 정리해봤다.

 

최소 스패닝 트리(Minimum Spanning Tree, MST)

• 주어진 그래프 내에서 가능한 모든 스패닝 트리 중에서 간선들의 가중치 합이 최소인 트리를 최소 스패닝 트리(이하 MST)라고 한다.
• 네트워크 설계, 알고리즘, 그래프 이론 등 다양한 분야에서 중요하게 사용한다.
• MST를 구하는 대표적인 알고리즘으로는 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘 두 가지가 있다.

 

최소 신장 트리

• "최소 스패닝(Spanning) 트리"와 "최소 신장(伸張) 트리"는 같은 개념이다.
• "스패닝 트리"와 "신장 트리"는 모두 주어진 그래프의 모든 정점을 포함하면서 사이클을 형성하지 않는 부분 그래프를 의미한다.
• "최소"라는 단어는 그 트리의 간선들의 가중치 합이 최소가 되는 트리를 의미한다.
• 최소 신장 트리(MST)를 구성하는 간선들이 단방향 그래프를 형성하지 않는 것에 대한 근본적인 이유는 신장 트리가 본질적으로 무방향 그래프이기 때문이다.
• MST의 목적은 주어진 그래프의 모든 노드를 최소 비용으로 연결하는 것이며, 이때 간선들은 무방향성을 가진다.

 

최소 신장 트리의 특성

• 무방향성: MST에서 각 간선은 두 노드를 서로 연결한다. 이 연결은 양방향성을 가짐. 즉, (u, v, w) 간선은 노드 u에서 v로의 연결 뿐만 아니라 v에서 u로의 연결도 의미한다.
• 비순환성: MST는 사이클을 포함하지 않는다. 그래프의 모든 노드를 포함하면서도 최소 비용을 유지하기 위해 사이클 형성을 피한다.
• 연결성: MST는 그래프의 모든 노드가 서로 연결되어 있어야 한다. 즉, 그래프의 어떤 노드에서도 다른 모든 노드로 이동이 가능해야 한다.

 

프림 알고리즘 (Prim's Algorithm)

시작 정점에서 출발하여, 점진적으로 MST를 확장해 나가는 방식으로 그래프의 모든 정점을 최소한의 비용으로 연결하는 문제를 해결한다.

 

예시 코드

import heapq

def prim(graph, start):
    visited = set()  # 이미 MST에 추가된 정점을 추적하는 집합
    min_heap = [(0, start)]  # (가중치, 정점) 튜플로 구성된 우선순위 큐
    mst_cost = 0  # 최소 스패닝 트리의 총 가중치

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)  # 가장 작은 가중치의 정점 선택
        if vertex not in visited:
            visited.add(vertex)  # 선택된 정점을 MST 집합에 추가
            mst_cost += weight  # 총 가중치에 해당 정점의 가중치 추가

            print(f"정점 {vertex}을(를) MST에 추가. 현재 MST 비용: {mst_cost}")

            for next_vertex, next_weight in graph[vertex]:
                if next_vertex not in visited:
                    # 인접한 정점을 우선순위 큐에 추가
                    heapq.heappush(min_heap, (next_weight, next_vertex))
                    print(f"정점 {vertex}에서 {next_vertex}로 가는 가중치 {next_weight} 간선을 큐에 추가")

    return mst_cost

# 그래프 예시 (인접 리스트 형태)
graph = {
    'A': [('B', 2), ('C', 3)],
    'B': [('A', 2), ('C', 1)],
    'C': [('A', 3), ('B', 1)]
}

# 프림 알고리즘 실행
mst_cost = prim(graph, 'A')
print("최종 MST 비용:", mst_cost)

 

출력 결과

정점 A을(를) MST에 추가. 현재 MST 비용: 0
정점 A에서 B로 가는 가중치 2 간선을 큐에 추가
정점 A에서 C로 가는 가중치 3 간선을 큐에 추가
정점 B을(를) MST에 추가. 현재 MST 비용: 2
정점 B에서 C로 가는 가중치 1 간선을 큐에 추가
정점 C을(를) MST에 추가. 현재 MST 비용: 3
최종 MST 비용: 3

 

참고) 그래프 형태

양방향(또는 무방향) 그래프의 예시

 

초기 설정

임의의 시작 정점을 선택하고, MST 집합(visited)을 빈 집합으로 초기화한다.

 

MST 집합 사용 이유

 

중복 방지

• 목적: 이미 MST에 포함된 정점을 재선택하는 것을 방지한다.
• 방법: MST 집합(visited)을 사용하여 이미 포함된 정점들을 추적한다.
• 이점: 알고리즘이 같은 정점을 여러 번 선택하는 것을 방지하여 MST를 올바르게 구성한다.

 

효율적인 탐색

• 목적: 이미 처리된 정점을 빠르게 식별하여 불필요한 연산을 줄인다.
• 방법: MST 집합을 확인하여 각 정점의 MST 포함 여부를 빠르게 판단한다.
• 이점: 알고리즘 실행 시간을 줄이며, 효율적인 탐색 가능하게 한다.

 

알고리즘의 정확성

• 목적: MST가 실제로 최소 가중치를 갖도록 보장한다.
• 방법: 이미 MST에 포함된 정점으로의 연결을 고려하지 않고, 각 단계에서 최적의 선택을 수행한다.
• 이점: 최종적으로 구성된 스패닝 트리가 최소 가중치 조건을 충족시키도록 보장한다.

 

MST 집합 구현

• set이나 bool 배열을 사용하여 구현한다.
• set을 사용할 경우 특정 정점의 포함 여부를 O(1) 시간 내에 확인할 수 있어 효율적이다.

 

반복 과정

1. visited에 포함되지 않은 정점 중 최소 가중치 간선을 통해 연결되는 정점을 선택한다.
2. 선택된 정점을 visited에 추가한다.
3. 선택된 정점에 연결된 간선들을 고려하여 최소 가중치 간선을 업데이트한다.

 

종료 조건

모든 정점이 visited에 포함될 때까지 반복한다.

 

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 가중치가 가장 작은 간선부터 차례대로 선택하여, 사이클을 형성하지 않는 한 MST에 추가하는 방식이다.

 

예시 코드

class UnionFind:
    # 유니온-파인드 클래스 정의
    def __init__(self, size):
        # 각 노드의 루트를 자기 자신으로 초기화
        self.root = [i for i in range(size)]

    def find(self, x):
        if self.root[x] == x:  # 노드 x의 루트 찾기
            return x

        # 경로 압축(재귀)을 사용하여 효율성을 높임
        self.root[x] = self.find(self.root[x])

        return self.root[x]

    def union(self, x, y):  # 두 노드 x, y의 루트를 찾아 연결
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:  # 두 노드 x, y의 루트가 다르면
            self.root[rootY] = rootX  # 서로 다른 노드이므로 두 노드를 연결

        # 이 때, 효율성을 높이기 위해 '랭크(rank)' 또는 '크기(size)' 기반의 최적화를 진행할 수 있음
        # 그러나 많은 코딩테스트 문제는 최적화된 유니온-파인드 알고리즘까지는 요구하지 않음

    def connected(self, x, y):
        # 두 노드가 같은 집합에 속하는지 확인
        # 다른 집합에 속해야지만 사이클이 형성되지 않음
        return self.find(x) == self.find(y)


# 크루스칼 알고리즘 함수 정의
def kruskal(graph, V):
    uf = UnionFind(V)  # 유니온-파인드 객체 초기화
    mst_cost = 0  # MST의 총 가중치
    mst_edges = []  # MST를 구성하는 간선들

    # 간선을 가중치 기준으로 오름차순 정렬
    graph.sort(key=lambda x: x[2])

    for edge in graph:  # 각 간선에 대해 순회
        u, v, weight = edge

        if not uf.connected(u, v):  # 사이클이 형성되지 않는 경우에만 간선을 추가
            uf.union(u, v)
            mst_cost += weight
            mst_edges.append(edge)

            print(f"간선 {u}-{v} (가중치 {weight})을 MST에 추가")

    return mst_cost, mst_edges


# 그래프 예시: 각 간선은 (u, v, weight) 형태로 표현
graph = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
V = 4  # 정점의 수

# 크루스칼 알고리즘 실행
mst_cost, mst_edges = kruskal(graph, V)
print("최소 스패닝 트리 비용:", mst_cost)
print("MST에 포함된 간선들:", mst_edges)

 

출력 결과

간선 2-3 (가중치 4)을 MST에 추가
간선 0-3 (가중치 5)을 MST에 추가
간선 0-1 (가중치 10)을 MST에 추가
최소 스패닝 트리 비용: 19
MST에 포함된 간선들: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

 

간선 정렬

모든 간선을 가중치에 따라 오름차순 정렬한다.

 

간선을 오름차순 정렬하는 이유

1. 최소 가중치 우선: 간선의 가중치는 연결 비용을 나타내므로, 가장 낮은 가중치를 가진 간선부터 선택하여 전체 비용을 최소화한다.
2. 효율적인 간선 선택: 간선을 오름차순으로 정렬하면, 알고리즘은 각 단계에서 가장 낮은 가중치를 가진 간선부터 차례대로 처리할 수 있다. 이는 알고리즘을 간단하고 효율적으로 만들며, 각 단계에서 최적의 선택을 보장한다.
3. 사이클 방지: 크루스칼 알고리즘에서는 사이클을 형성하는 간선을 피해야 한다. 가중치가 낮은 간선부터 선택하는 과정에서 사이클을 형성하는지 여부를 검사하여, MST가 트리 구조를 유지하도록 한다.

 

반복 과정

1. 가중치가 가장 작은 간선을 선택한다.
2. 선택된 간선이 사이클을 형성하지 않으면, MST에 추가한다.
3. 유니온-파인드(Union-Find) 알고리즘을 사용하여 사이클 여부 판단한다.

 

종료 조건

모든 간선을 확인할 때까지 반복한다.

 

MST 구현을 위한 알고리즘 작성 방법

두 알고리즘 모두 MST를 구하는 효율적인 방법이지만 문제의 특성과 그래프의 크기, 구현의 용이성과 실행 시간의 효율성을 고려하면서 상황에 따라 적합한 알고리즘을 선택하는 것이 중요하다.

 

프림 알고리즘

• 간선의 개수가 많은 밀집 그래프(dense graph)에서 효과적이다.
• 우선순위 큐(Priority Queue)를 사용하여 효율적으로 구현한다.

 

프림 알고리즘을 추천하는 경우

• 그래프가 밀집(dense)한 경우: 노드 간에 많은 수의 간선이 있는 경우이다.
• 그래프의 노드 수 대비 간선 수가 많을 때이다.
• 우선순위 큐(힙)를 활용하는 방식으로 구현할 때: 특정 노드에서 시작하여 가장 가까운 노드를 찾아가며 MST를 구성한다.

 

프림 알고리즘과 양방향 간선 데이터

요약: 알고리즘의 특성상 각 노드에서 인접한 노드를 쉽게 파악하고 접근할 수 있도록 하기 위함이다.

다음과 같은 자세한 이유로 프림 알고리즘은 양방향 간선 데이터가 유용하다.

1. 접근성: 프림 알고리즘은 현재 MST에 인접한 노드 중에서 가장 낮은 가중치를 가진 간선을 선택한다. 양방향 간선 데이터를 사용하면 어느 노드에서든 인접한 모든 노드로의 접근이 용이하다.
2. 간편한 구현: 각 노드에서 출발하는 모든 간선을 나열함으로써, 알고리즘을 구현할 때 각 노드에 대한 인접 노드를 쉽게 파악한다.
3. 무방향성 고려: 실제로 프림 알고리즘은 무방향 그래프를 대상으로 하므로, 간선은 양방향으로 고려한다. 이를 나타내기 위해 양방향 간선 데이터를 사용하는 것이 적합하다.

 

무방향 그래프 사용 예시 (양방향 간선 정보)

각 노드에 대해 양방향의 간선 정보가 포함된다.

graph = {
    'A': [('B', 2), ('C', 3)],
    'B': [('A', 2), ('C', 1)],
    'C': [('A', 3), ('B', 1)]
}

 

단방향 그래프 사용 예시 (단방향 간선 정보)

각 노드에서 출발하는 간선만을 포함한다.

graph = {
    'A': [(2, 'A', 'B'), (3, 'A', 'C')],
    'B': [(1, 'B', 'C')],
    'C': []
}

 

크루스칼 알고리즘

• 간선의 개수가 적은 희소 그래프(sparse graph)에서 효과적이다.
• 유니온-파인드 알고리즘을 사용하여 사이클 여부 판단한다.

 

크루스칼 알고리즘을 추천하는 경우

• 그래프가 희소(sparse)한 경우: 노드 간에 상대적으로 적은 수의 간선이 있는 경우이다.
• 간선의 수가 노드 수에 비해 상대적으로 적을 때: 이 경우 크루스칼 알고리즘이 더 효율적이다.
• 유니온 파인드(Union Find) 자료구조를 활용: 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성한다.

 

크루스칼 알고리즘과 단방향 간선 데이터

요약: 단방향 간선 데이터만으로도 전체 그래프의 구조를 충분히 표현할 수 있으며, 이는 알고리즘의 효율성을 높이는데 기여한다.

단방향 간선 데이터의 사용은 다음과 같은 자세한 이유 때문에 유용하다.

1. 중복 간선 회피: 크루스칼 알고리즘에서 그래프의 모든 간선을 고려할 때, 각 간선은 무방향으로 취급되므로, 양방향으로 나열된 간선은 중복을 의미한다. 따라서 단방향 간선 데이터만으로도 충분하다.
2. 효율성: 간선을 정렬하고 사이클을 확인하는 과정에서 중복 간선을 제거함으로써, 알고리즘의 효율성을 높인다.
3. 사이클 확인: 크루스칼 알고리즘에서 중요한 것은 사이클을 형성하지 않는 간선의 선택. 이는 간선의 방향성과 무관하게 수행한다.

 

무방향 그래프 사용 예시 (양방향 간선 정보)

각 간선을 양방향으로 나타내지만, 실제로는 각 간선이 무방향으로 취급된다.

graph = [
    (0, 1, 10), (1, 0, 10),
    (0, 2, 6), (2, 0, 6),
    (0, 3, 5), (3, 0, 5),
    (1, 3, 15), (3, 1, 15),
    (2, 3, 4), (3, 2, 4)
]

 

단방향 그래프 사용 예시 (단방향 간선 정보)

각 간선은 한 번씩만 나열한다.

graph = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

 

간선 개수 대소 구분 기준

대체로 그래프의 정점(vertex) 수에 대한 간선(edge) 수의 비율에 의해 결정한다. 구체적인 기준은 상대적이며 문맥에 따라 다를 수 있지만, 일반적인 지침은 아래와 같다.

 

밀집 그래프 (Dense Graph)

• 간선의 수가 정점의 수에 비해 상대적으로 많은 그래프이다.
• 간선의 수가 V개의 정점에 대해 (V*(V-1))/2에 가까운 완전 그래프(complete graph)이다.
• 각 정점이 다른 모든 정점과 연결된 경우이다.

 

희소 그래프 (Sparse Graph)

• 간선의 수가 정점의 수에 비해 상대적으로 적은 그래프이다.
• 간선의 수가 V개의 정점에 대해 최대 V 또는 V log V 정도인 그래프이다.
• 트리(tree)는 희소 그래프의 한 예시이다.

 

자료 구조에서 "노드(Node)"와 "정점(Vertex)"

두 용어는 상황에 따라 다르게 사용될 수 있지만, 일반적으로 상호 교환적으로 사용될 수 있는 경우도 많다.

 

노드(Node)

개념

트리나 연결 리스트와 같이 계층적이거나 선형적인 자료 구조의 기본 요소이다.

• 데이터 요소와 하나 또는 여러 개의 참조(자식 노드, 다음 노드 등)를 포함한다.
• 트리에서 각 노드는 일반적으로 부모-자식 관계를 가지는 요소를 나타낸다.

 

예시 코드

class TreeNode:
    def __init__(self, value):
        self.value = value # 트리 노드의 값을 의미
        self.children = []

 

정점(Vertex)

개념

그래프에서의 위치나 연결 관계를 강조하는 데 사용되는 자료 구조의 기본 요소이다.

• 주로 그래프 이론에서 사용되는 용어이다.
• 간선(Edge)을 통해 다른 정점과 연결되며, 그래프 기본 요소를 구성한다.
• 정점은 그래프 내에서의 위치나 연결 상태를 나타내는 데 중점을 둔다.

 

예시 코드

class GraphVertex:
    def __init__(self, key):
        self.key = key # 그래프의 정점을 의미
        self.adjacent = []

 

Node와 Vertex 값의 변수명

보통 value, data 또는 key와 같은 영단어로 변수명을 표현하나 그 값이 무엇을 의미하는지에 따라 달라질 수 있다.

 

value

• 노드나 정점에 저장된 '값'을 나타내는 가장 일반적인 용어이다.
• 특히 그 값이 어떤 특정한 유형의 데이터를 대표할 때 사용한다.

 

data

• 'data'는 노드나 정점에 저장된 정보를 나타낸다.
• value와 유사하게 사용되며, 노드나 정점이 담고 있는 정보나 객체를 의미한다.

 

key

• 특히 그래프 또는 트리에서 노드나 정점을 구분하는 데 사용되는 고유한 식별자이다.
• 예를 들어, 이진 탐색 트리에서 각 노드의 키는 정렬이나 탐색을 위한 기준이 된다.

 

유니온-파인드(Union-Find) 알고리즘

• 집합의 연합(Union)과 대표자 찾기(Find)를 효율적으로 수행하는 알고리즘이다.
• 주로 그래프의 사이클을 확인하거나, 여러 집합 간의 관계를 관리하는 데 사용한다.
• 크루스칼 알고리즘에서 사이클 형성 여부를 판단하는 데 유용하게 사용한다.

 

핵심 함수

1. Find 함수

def find(self, x):
  if self.root[x] == x:  # 노드 x의 루트 찾기
      return x

  # 경로 압축(재귀)을 사용하여 효율성을 높임
  self.root[x] = self.find(self.root[x])

  return self.root[x]

대표자를 찾는 과정에서, 각 원소의 포인터를 직접 최종 대표자로 업데이트하여, 다음 조회 시 시간을 단축한다.

• 목적: 특정 원소가 속한 집합의 대표자(루트)를 찾음
• 작동 원리: 각 원소는 자신이 속한 집합의 대표자를 가리키는 포인터를 따라가며 최종 대표자(루트)를 찾는다.

 

find 함수에 대한 이해

1. find 함수가 같은 루트를 반환한다면, 이는 두 원소가 같은 집합에 속한다는 것을 논리적으로 증명한다.
2. 집합의 정의와 find 함수의 작동 원리를 이해하고 왜 사이클 형성 여부를 판단하는 데 사용하는지 학습한다.

• 집합: 유니온-파인드 알고리즘에서, 각 집합은 고유한 '루트' 또는 '대표자'에 의해 식별. 집합의 모든 원소는 이 루트로 직간접적으로 연결한다.
• Find 함수: find 함수는 주어진 원소로부터 시작하여 루트를 찾음. 이 과정에서, 각 원소는 다른 원소를 가리키거나 최종적으로 자신의 루트를 가리킨다.

 

같은 집합에 속함을 증명하는 과정

1. 가정: 두 원소 x와 y가 있으며, find(x)와 find(y)가 같은 값을 반환한다고 가정한다. 즉, find(x) == find(y) 이다.
2. 루트로의 경로: find 함수는 x와 y로부터 시작하여 각각의 루트를 찾는다. 이 과정은 연결된 경로를 따라 루트에 도달할 때까지 계속된다.
3. 같은 루트를 공유함: 'find' 함수가 x와 y에 대해 같은 루트를 반환한다면, 이는 x와 y가 동일한 경로를 통해 같은 루트에 도달했다는 것을 의미한다. 즉, x와 y는 동일한 집합에 속한다.

 

시각적인 설명

   루트
    |
    x
   / \
  a   b
     / \
    y   c

• 위의 그림에서, x와 y는 같은 루트로 연결되어 있다.
• find(x)와 find(y) 모두 같은 루트를 가리키므로, x와 y는 같은 집합에 속한다.

  루트
  / \
a    b
|   / \
x  y   c

• 위의 그림에서, x와 y는 서로 다른 부모 노드(a와 b)를 가지지만, 둘 다 같은 루트에 연결되어 있다.
• 따라서 x와 y는 같은 집합에 속한다.

 

2. Union 함수

def union(self, x, y):  # 두 노드 x, y의 루트를 찾아 연결
  rootX = self.find(x)
  rootY = self.find(y)

  if rootX != rootY:  # 두 노드 x, y의 루트가 다르면
      self.root[rootY] = rootX  # 서로 다른 노드이므로 두 노드를 연결

  # 이 때, 효율성을 높이기 위해 '랭크(rank)' 또는 '크기(size)' 기반의 최적화를 진행할 수 있음
  # 그러나 많은 코딩테스트 문제는 최적화된 유니온-파인드 알고리즘까지는 요구하지 않음

이미 연결된 노드들을 한 집합으로 관리하여 사이클 형성을 방지한다.

• 목적: 두 개의 원소가 속한 집합을 하나로 병합한다.
• 작동 원리: 두 원소의 대표자를 찾고, 하나의 대표자를 다른 대표자에 연결하여 두 집합을 합친다.

 

union 함수에 대한 이해

두 개의 원소가 속한 집합을 하나로 합치는 역할 수행한다. 이 함수는 크루스칼 알고리즘에서 사이클 형성 여부를 판단하는 데 핵심적인 역할을 한다.

 

역할 및 작동 원리

1. 역할: 두 원소가 속한 집합을 하나로 합친다.
2. 작동 원리: find 함수를 사용하여 두 원소 x와 y의 루트를 찾고 x의 루트를 y의 루트에 연결한다(또는 그 반대이다). 이렇게 함으로써 두 집합을 병합한다.
3. 코드 설명

def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)
    if rootX != rootY:
        self.root[rootY] = rootX

• self.find(x)와 self.find(y)는 각각 x와 y의 루트를 찾는다.
• 만약 두 루트가 다르다면(rootX != rootY), 두 집합은 서로 다른 집합이다.
• 이 경우 y의 루트(rootY)를 x의 루트(rootX)에 연결하여 두 집합을 하나로 합친다.

 

union 함수와 사이클 형성의 관계

• 크루스칼 알고리즘에서 간선을 하나씩 추가할 때마다 union 함수를 사용하여 두 노드를 연결한다.
• 만약 두 노드가 이미 같은 집합에 속해 있다면(connected 함수로 확인), 이 간선을 추가하면 사이클이 형성된다. 따라서 이 경우 간선을 추가하지 않는다.
• 반대로 두 노드가 다른 집합에 속해 있다면, 이 간선을 추가해도 사이클이 형성되지 않는다. 이 경우 union 함수를 사용하여 이 두 집합을 병합한다.

 

3. Connected 함수

def connected(self, x, y):
  # 두 노드가 같은 집합에 속하는지 확인
  # 다른 집합에 속해야지만 사이클이 형성되지 않음
  return self.find(x) == self.find(y)

• 목적: 두 원소가 같은 집합에 속해 있는지 확인한다.
• 작동 원리: 두 원소의 대표자(루트)가 같은지 비교하여, 같은 집합에 속해 있는지 확인한다.

 

크루스칼 알고리즘에서의 사용

union과 find를 통해 각 노드의 연결 상태를 관리하고, connected를 사용하여 이미 연결된 노드(즉, 사이클을 형성할 가능성이 있는 노드)를 건너뛰어 MST를 구성한다.

1. 간선을 가중치 오름차순으로 정렬한 후, 각 간선을 순회한다.
2. 두 노드가 아직 연결되지 않았다면(즉, 같은 집합에 속하지 않았다면) 해당 간선을 MST에 추가한다.
3. 이 과정에서 find와 union 함수를 사용하여 사이클 형성을 방지한다.

 

그래프 간선의 방향성

그래프 관련 알고리즘 문제는 크게 방향성이 중요한 문제와 방향성이 중요하지 않은 문제로 구분할 수 있다.

• 방향성이 중요한 문제들은 주로 그래프의 방향성이 문제 해결의 핵심 요소로 작용한다. 예를 들어 단방향 그래프에서는 특정한 문제 상황을 해결하는 데 초점을 둔다.
• 방향성이 중요하지 않은 문제들은 그래프의 연결성만을 고려하며, 노드 간의 이동 방향에 제약이 없는 상황을 다룬다.

이러한 구분은 알고리즘 문제를 접근하고 해결할 때 중요한 기준으로 작용하며 그래프 간선의 방향성 선택은 구현의 복잡성, 메모리 사용량, 그리고 개발자의 선호도에 따라 달라질 수 있다.

 

방향성이 중요한 문제 유형

단방향 그래프 탐색

• 특정 노드에서 시작하여 다른 노드로 이동하는 경로 탐색 문제이다.
• 예: 최단 경로 찾기, 사이클 감지, 위상 정렬

 

네트워크 플로우

• 특정 노드(소스)에서 다른 노드(싱크)로 최대 흐름을 찾는 문제이다.
• 예: 최대 흐름 문제, 최소 컷 문제

 

강한 연결 요소 탐색

• 단방향 그래프에서 각 노드가 서로 연결되어 있는 구성 요소를 찾는 문제이다.
• 예: 코사라주 알고리즘, 타잔 알고리즘

 

방향성이 중요하지 않은 문제 유형

무방향 그래프 탐색

• 양방향으로 이동할 수 있는 그래프에서 경로 탐색 문제이다.
• 예: 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 연결 요소 찾기

 

최소 신장 트리(MST)

• 그래프의 모든 노드를 최소 비용으로 연결하는 트리를 찾는 문제이다.
• 예: 프림 알고리즘, 크루스칼 알고리즘

 

무방향 사이클 탐색

• 무방향 그래프에서 사이클이 있는지 확인하는 문제이다.
• 예: 무방향 그래프에서의 사이클 탐지

 

단방향성에 대한 오해

MST를 통해 얻은 간선들을 사용하여 그래프를 그릴 때, 각 간선은 양방향으로 고려해야 한다. MST의 정확한 구성은 주어진 그래프의 모든 노드를 최소 비용으로 연결하는 것이며, 이는 간선의 방향성과는 무관하다.

• 최소 신장 트리는 그래프 내의 모든 노드를 포함하는 하나의 연결 트리를 형성한다.
• 이 트리는 무방향 그래프이므로, 간선들이 단방향으로만 연결되지는 않는다.
• 예를 들어, 간선 (0, 3, 5)는 노드 0에서 3으로의 연결 뿐만 아니라 3에서 0으로의 연결도 동시에 나타낸다.

 

무방향성의 의미

• 무방향 그래프에서 간선 (A, B, w)는 A에서 B로의 연결 뿐만 아니라 B에서 A로의 연결도 동시에 의미한다. 따라서, 가중치는 양방향 간선에 대해 동일하게 적용하다.
• 프로그래밍 구현에서 이를 양방향으로 나열하는 것은 단지 구현의 편의를 위한 것이며, 실제로는 방향성이 없는 간선으로 간주된다.
• 프림 알고리즘 예시에서 간선 정보를 양방향으로 제공하는 것은 구현 상의 편의와 명확성을 위한 것이다. 실제로는 이 간선들이 무방향성을 가진다는 것을 의미한다. 즉, A에서 B로 가는 가중치와 B에서 A로 가는 가중치는 동일하게 적용한다.

 

양방향 간선 정보 포함의 이유

MST 문제에서 무방향 그래프를 표현할 때, 사실상 한 방향의 간선 정보만 있어도 충분하다. 각 간선은 무방향성을 가지기 때문에, 한 쪽 방향의 정보만으로도 전체 그래프의 구조를 완전히 표현 가능하다.

 

그럼에도 불구하고 양방향 간선 정보를 모두 포함시키는 이유는 다음과 같다.

 

구현의 용이성

• 프로그래밍에서 그래프를 구현할 때, 특정 노드에서 출발하는 모든 간선을 나열하는 것이 일반적이다.
• 프로그래밍 자료구조를 이용하여 각 노드에서 이동 가능한 다른 노드와 그 가중치를 쉽게 관리할 수 있도록 한다.
• 이 방식은 프림 알고리즘과 같은 그래프 알고리즘을 구현할 때 간편하다.

 

명확성과 가독성

• 그래프의 전체 구조를 한눈에 파악하기 쉽다.
• 각 노드에서 출발하여 도달할 수 있는 모든 노드와 그 가중치를 명시적으로 표현함으로써, 그래프의 구조를 이해하기 쉽게 만든다.

 

알고리즘 특성 고려

• 프림 알고리즘의 경우, 시작 노드에서 인접한 노드로 확장해 가면서 MST 구성한다.
• 이 과정에서 각 노드에서 출발하는 간선 정보가 명확히 제공되면, 어떤 노드로 확장할 수 있는지 쉽게 파악 가능하다.

 

한 방향 간선 정보만 포함시키는 경우

• 실제로 한 방향의 간선 정보만으로도 MST 알고리즘을 구현하는 것은 가능하다. 이 경우, 그래프의 메모리 사용량을 줄일 수 있고 각 노드에서 출발하는 간선의 수도 감소한다.
• 그러나 이 방식은 각 노드에서 인접한 노드를 찾는 데 추가적인 논리를 요구할 수 있으며, 전체 그래프 구조의 파악이 다소 어려워질 수 있다.

 

마치며

해... 해치웠다!

 

참 끈질긴 녀석이었지만, 이론 공부를 쫙 하고 보니 머릿속에 MST 푸는 방법이 이해가 되어 문제 자체는 쉽게 풀렸다.

 

아래는 정답으로 채점된 코드이다.

import sys


class UnionFind:
    # 유니온-파인드 클래스 정의
    def __init__(self, size):
        # 각 노드의 루트를 자기 자신으로 초기화
        self.root = [i for i in range(size + 1)]

    def find(self, x):
        if self.root[x] == x:  # 노드 x의 루트 찾기
            return x

        # 경로 압축(재귀)을 사용하여 효율성을 높임
        self.root[x] = self.find(self.root[x])

        return self.root[x]

    def union(self, x, y):  # 두 노드 x, y의 루트를 찾아 연결
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:  # 두 노드 x, y의 루트가 다르면
            self.root[rootY] = rootX  # 서로 다른 노드이므로 두 노드를 연결

        # 이 때, 효율성을 높이기 위해 '랭크(rank)' 또는 '크기(size)' 기반의 최적화를 진행할 수 있음
        # 그러나 많은 코딩테스트 문제는 최적화된 유니온-파인드 알고리즘까지는 요구하지 않음

    def connected(self, x, y):
        # 두 노드가 같은 집합에 속하는지 확인
        # 다른 집합에 속해야지만 사이클이 형성되지 않음
        return self.find(x) == self.find(y)


# 크루스칼 알고리즘 함수 정의
def kruskal(graph, V):
    uf = UnionFind(V)  # 유니온-파인드 객체 초기화
    mst_cost = 0  # MST의 총 가중치

    # 간선을 가중치 기준으로 오름차순 정렬
    graph.sort(key=lambda x: x[2])

    for edge in graph:  # 각 간선에 대해 순회
        u, v, weight = edge

        if not uf.connected(u, v):  # 사이클이 형성되지 않는 경우에만 간선을 추가
            uf.union(u, v)
            mst_cost += weight

    return mst_cost


# V: 정점 수, E: 간선 수
V, E = map(int, sys.stdin.readline().split())

graph = []

# 그래프 예시: 각 간선은 (u, v, weight) 형태로 표현
for _ in range(E):
    graph.append(list(map(int, sys.stdin.readline().split())))

print(kruskal(graph, V))

 

앞으로도 종종 막히는 문제가 알고리즘 개념 때문에 막히는 경우라면 이렇게 이론 정리를 먼저 한 후에 문제를 푸는 습관을 들일 예정이다.