2026-07-22 TIL (102일차)

코딩 테스트 핵심 그래프 이론 (서로소 집합, 크루스칼, 위상 정렬)

개요

코딩 테스트에서 자주 출제되는 핵심 그래프 알고리즘인 서로소 집합(Disjoint Set), 크루스칼(Kruskal), 위상 정렬(Topological Sort) 세 가지의 기본 개념과 C++ 구현 방법을 정리했다.

---

1. 서로소 집합 (Disjoint Sets) / Union-Find 자료구조

공통 원소가 없는 두 집합을 다루기 위한 자료구조로, 트리 자료구조를 이용해 집합을 표현한다.

• 주요 연산:
  • Find (찾기): 특정한 원소가 속한 집합(루트 노드)을 찾는 연산.
  • Union (합집합): 두 원소가 포함된 집합을 하나의 집합으로 합치는 연산 (보통 더 작은 번호의 노드를 부모로 설정).
• 최적화 (경로 압축 - Path Compression):
  • 기본적인 Find 함수는 최악의 경우 트리 깊이만큼 시간이 걸린다. 이를 해결하기 위해 재귀적으로 호출된 결과(루트 노드)를 바로 부모 노드로 갱신하여 경로를 단축한다.

C++ 구현: 서로소 집합 & 경로 압축

#include <iostream>
using namespace std;

int v, e;
int parent_node[100001];

// 특정 원소가 속한 집합을 찾기 (경로 압축 기법 적용)
int findParent(int x) {
    // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if (parent_node[x] != x) {
        parent_node[x] = findParent(parent_node[x]);
    }
    return parent_node[x];
}

// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent_node[b] = a;
    else parent_node[a] = b;
}

2. 무방향 그래프에서의 사이클 판별

서로소 집합(Union-Find)을 활용하면 무방향 그래프 안에서 사이클(Cycle)이 발생하는지 판별할 수 있다. (참고: 방향 그래프의 사이클은 DFS를 이용한다.)

• 판별 알고리즘:
  • 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다(Find).
  • 루트 노드가 서로 다르다면 두 노드를 합친다(Union).
  • 루트 노드가 이미 같다면 사이클이 발생한 것이다.

C++ 구현: 사이클 판별 로직

bool cycle = false;

for (int i = 0; i < e; i++) {
    int a, b;
    cin >> a >> b;
    // 사이클이 발생한 경우 종료
    if (findParent(a) == findParent(b)) {
        cycle = true;
        break;
    }
    // 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else {
        unionParent(a, b);
    }
}

if (cycle) cout << "사이클이 발생했습니다.\n";
else cout << "사이클이 발생하지 않았습니다.\n";

---

3. 최소 신장 트리 (Kruskal 알고리즘)

신장 트리(Spanning Tree)란 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프다. 이 중 간선 비용의 합이 가장 적은 트리를 찾는 알고리즘이 크루스칼(Kruskal) 알고리즘이다.

• 동작 과정 (그리디 방식):
  1. 모든 간선을 비용(Cost) 기준으로 오름차순 정렬한다.
  2. 간선을 하나씩 확인하며 사이클을 발생시키는지 확인한다.
  3. 사이클이 발생하지 않는 간선만 트리에 포함시킨다.
• 시간 복잡도: O(E log E) (간선 정렬에 드는 시간이 지배적이다).

C++ 구현: 크루스칼 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int v, e;
int parent_node[100001];
// 간선 정보를 담을 벡터 (비용, 노드 A, 노드 B)
vector<pair<int, pair<int, int>>> edges;
int result = 0;

int findParent(int x) {
    if (parent_node[x] != x) parent_node[x] = findParent(parent_node[x]);
    return parent_node[x];
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent_node[b] = a;
    else parent_node[a] = b;
}

int main() {
    cin >> v >> e;
    for (int i = 1; i <= v; i++) parent_node[i] = i;

    for (int i = 0; i < e; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        edges.push_back({cost, {a, b}});
    }

    // 1. 간선을 비용순으로 오름차순 정렬
    sort(edges.begin(), edges.end());

    // 2. 간선을 하나씩 확인하며 최소 신장 트리 만들기
    for (int i = 0; i < edges.size(); i++) {
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        
        // 사이클이 발생하지 않는 경우에만 집합에 포함
        if (findParent(a) != findParent(b)) {
            unionParent(a, b);
            result += cost;
        }
    }

    cout << "최소 비용: " << result << '\n';
    return 0;
}

---

4. 위상 정렬 (Topological Sorting)

사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서, 방향성에 거스르지 않도록 노드를 순서대로 나열하는 알고리즘이다. (예: 선수 과목 학습 순서 등)

• 진입차수(Indegree): 특정 노드로 들어오는 간선의 개수.
• 동작 과정 (Queue 사용):
  1. 진입차수가 0인 모든 노드를 Queue에 넣는다.
  2. Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. (연결된 노드의 진입차수를 1 감소시킨다.)
  3. 새롭게 진입차수가 0이 된 노드를 Queue에 넣는다.
  4. Queue가 빌 때까지 반복한다.
• 특징:
  • 모든 원소를 방문하기 전에 Queue가 비어버린다면 사이클이 존재한다는 의미다.
  • 한 번에 여러 노드가 Queue에 들어갈 수 있으므로, 결과(위상 정렬 순서)가 여러 개 존재할 수 있다.
• 시간 복잡도: O(V + E)

C++ 구현: 위상 정렬 알고리즘

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int v, e;
int indegree[100001];      // 모든 노드에 대한 진입차수는 0으로 초기화
vector<int> graph[100001]; // 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트

void topologySort() {
    vector<int> result; // 알고리즘 수행 결과를 담을 리스트
    queue<int> q;

    // 1. 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for (int i = 1; i <= v; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    // 2. 큐가 빌 때까지 반복
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        result.push_back(now);

        // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for (int i = 0; i < graph[now].size(); i++) {
            int next = graph[now][i];
            indegree[next] -= 1;
            // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if (indegree[next] == 0) {
                q.push(next);
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << '\n';
}

int main() {
    cin >> v >> e;
    
    // 방향 그래프의 모든 간선 정보 입력받기
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b); // 정점 A에서 B로 이동 가능
        indegree[b] += 1;      // B의 진입차수 1 증가
    }

    topologySort();
    
    return 0;
}