[태그:] DFS

학습 목표

이번 주차를 마치면 다음을 할 수 있습니다.

• 그래프 용어(정점, 간선, 차수, 방향, 가중치)를 정확히 쓰고, 현실의 문제를 그래프로 옮길 수 있다
• 인접 행렬과 인접 리스트로 그래프를 저장하고, 메모리와 시간이 어떻게 달라지는지 실제 숫자로 설명할 수 있다
• DFS(스택)와 BFS(큐)를 구현하고, 큐와 스택의 내용을 단계별로 추적할 수 있다
• visited 배열을 빼먹으면 정확히 무슨 일이 일어나는지 실험으로 확인했다
• 위상 정렬로 의존성 순서를 구하고 사이클을 감지할 수 있다
• 다익스트라, 벨만-포드, 플로이드-워셜을 구분해 쓰고, 각각의 함정을 직접 밟아 봤다
• Union-Find와 크루스칼, 프림으로 최소 신장 트리를 구할 수 있다

들어가며

스마트폰 내비게이션에 목적지를 넣으면 1초도 안 되어 경로가 나옵니다. 우리나라에는 도로가 수십만 개 있는데, 그 모든 조합을 다 따져 본 걸까요? 페이스북은 어떻게 “알 수도 있는 사람”을 골라 낼까요? 그리고 make 는 어떻게 파일 수백 개의 빌드 순서를 정하고, 순환 참조가 있으면 알아챌까요?

세 질문의 답은 하나입니다. 그래프(graph) 입니다. 도시와 도로, 사람과 친구 관계, 파일과 의존 관계는 모두 “점”과 “점을 잇는 선”으로 그릴 수 있고, 그렇게 그려 놓으면 같은 알고리즘으로 풀립니다.

그래프는 정점(vertex)과 간선(edge)의 집합입니다. 규칙은 그게 전부입니다. 12주차의 트리는 “루트가 하나, 부모는 하나, 사이클 없음”이라는 제약이 있었지만, 그래프에는 그런 제약이 없습니다. 사이클이 있어도 되고, 끊어진 섬이 있어도 되고, 선에 방향이나 숫자가 붙어도 됩니다. 그래서 트리는 그래프의 특수한 경우이고, 트리에서 배운 순회가 이번 주에 그대로 확장됩니다.

그리고 반가운 소식이 있습니다. 이번 주는 재료의 총집합입니다. BFS에 11주차의 큐가, DFS에 스택이, 다익스트라에 12주차의 힙이, 인접 리스트에 10주차의 연결 리스트가 그대로 들어갑니다. 새로 배울 자료구조는 거의 없습니다. 새로운 것은 이미 가진 것들을 조합하는 방법입니다.

이 글은 깁니다. 예제 아홉 개와 프로젝트 세 개가 있고, 예제마다 “이걸 바꾸면 어떻게 될까” 실험이 붙어 있습니다. 실험 결과는 전부 실제로 돌려서 얻은 것입니다. 특히 일부러 망가뜨리는 실험(방문 표시를 빼면, 루프 순서를 바꾸면, 무한대에 INT_MAX 를 쓰면)을 꼭 직접 해 보세요. 그래프 코드의 버그는 컴파일러가 잡아 주지 않고, 실행해도 그럴싸한 답이 나오는 경우가 많아서, 어떻게 틀리는지를 미리 봐 둬야 나중에 알아볼 수 있습니다.

예제 코드는 week14/examples/ 와 week14/projects/ 에 있습니다. week14 폴더에서 make 를 치면 전부 build/ 아래에 빌드됩니다. 하나씩 컴파일하려면 늘 쓰던 명령입니다.

$ cd week14
$ gcc -Wall -Wextra -std=c11 -g examples/graph_repr.c -o build/graph_repr

1. 용어 먼저 정리하기

그래프는 용어가 많습니다. 앞으로 계속 나올 것들이니 한 번에 정리하고 갑니다. SNS의 친구 관계를 예로 들겠습니다.

용어	뜻	SNS로 비유하면
정점(vertex, node)	그래프의 점	사용자 한 명
간선(edge)	두 정점을 잇는 선	친구 관계 하나
인접(adjacent)	간선으로 직접 이어진 관계	직접 친구
차수(degree)	한 정점에 붙은 간선 수	친구 수
경로(path)	정점들을 간선으로 이어 간 순서	친구의 친구의 친구…
사이클(cycle)	출발점으로 되돌아오는 경로	A의 친구 B, B의 친구 C, C의 친구 A
연결 성분(connected component)	서로 닿을 수 있는 정점들의 덩어리	완전히 분리된 커뮤니티

정점 수는 관례상 V, 간선 수는 E 로 씁니다. 알고리즘의 시간을 “O(V + E)” 처럼 표현할 때 이 글자들이 나옵니다.

차수에는 재미있는 성질이 하나 있습니다. 모든 정점의 차수를 더하면 간선 수의 정확히 2배입니다. 간선 하나가 양 끝 정점의 차수를 하나씩 올리기 때문입니다. 친구 관계 100개가 있는 SNS에서 모든 사람의 친구 수를 더하면 반드시 200입니다. 이 성질은 2절에서 인접 리스트의 메모리를 계산할 때 바로 쓰입니다.

그래프의 종류를 가르는 축은 두 개입니다.

방향의 유무

• 무방향 그래프: 간선에 방향이 없습니다. 친구 관계처럼 A가 B의 친구면 B도 A의 친구입니다.
• 방향 그래프(directed graph, digraph): 간선에 방향이 있습니다. 트위터 팔로우처럼 A가 B를 팔로우해도 B는 A를 팔로우하지 않을 수 있습니다. 과목의 선수 관계도 방향 그래프입니다. C기초를 들어야 자료구조를 들을 수 있지, 그 반대가 아니니까요.

가중치의 유무

• 무가중치 그래프: 간선은 그냥 “연결됨”이라는 뜻입니다.
• 가중치(weight) 그래프: 간선마다 숫자가 붙습니다. 거리, 시간, 요금, 대역폭 등입니다.

이 두 축의 조합에 따라 쓸 수 있는 알고리즘이 달라집니다. 무가중치면 BFS로 최단 경로를 구할 수 있지만, 가중치가 붙으면 다익스트라가 필요합니다. 오늘 배울 알고리즘을 고르는 첫 번째 기준이 바로 이것입니다.

	무가중치	가중치
무방향	친구 관계	도로망(거리)
방향	팔로우, 웹 링크	항공 노선(요금), 환율

트리는 그래프의 특수한 경우입니다. 정확히는 “사이클이 없고 연결된 무방향 그래프”가 트리입니다. 정점이 V개인 트리의 간선은 항상 V − 1개입니다. 12주차에 배운 트리 순회가 오늘 배울 DFS와 BFS의 특수한 경우인 이유가 여기 있습니다. 다만 그래프에는 트리에 없는 것이 하나 있고(사이클), 그 하나가 코드를 어떻게 바꾸는지가 3절의 주제입니다.

직접 해 보기: 종이에 여러분 친구 다섯 명을 점으로 그리고, 서로 아는 사람끼리 선을 그어 보세요. 그 그림이 그래프입니다. 선을 세어 보고, 각 사람의 선 개수를 모두 더해 보세요. 선 개수의 2배가 나올 겁니다.

2. 그래프 표현: 행렬 vs 리스트

2.1 두 가지 방법

종이 위의 그림을 컴퓨터 메모리에 넣으려면 두 가지 방법이 있습니다.

인접 행렬(adjacency matrix) 은 V × V 크기의 2차원 배열입니다. matrix[u][v] 가 1이면 u와 v 사이에 간선이 있다는 뜻입니다. 8주차 구조체 안에 4주차의 2차원 배열을 넣은 것뿐입니다.

    0 1 2 3 4 5
  0 . 1 1 . . .        0번은 1, 2와 연결
  1 1 . 1 1 . .
  2 1 1 . . . .
  3 . 1 . . 1 .
  4 . . . 1 . .
  5 . . . . . .        5번은 외톨이

무방향 그래프의 행렬은 대각선을 기준으로 대칭입니다. matrix[0][1] 이 1이면 matrix[1][0] 도 1이니까요.

인접 리스트(adjacency list) 는 정점마다 “이웃 목록”을 10주차의 연결 리스트로 들고 있는 방식입니다.

  0: 2 -> 1 -> NULL
  1: 3 -> 2 -> 0 -> NULL
  2: 1 -> 0 -> NULL
  3: 4 -> 1 -> NULL
  4: 3 -> NULL
  5: NULL

다음 예제는 같은 그래프를 두 방식으로 저장하고, 연산과 메모리를 비교합니다.

examples/graph_repr.c:

/*
 * graph_repr.c - 그래프 표현: 인접 행렬 vs 인접 리스트
 * 14주차: 그래프 자료구조와 탐색
 *
 * 그래프 = 정점(vertex)들과 그들을 잇는 간선(edge)들.
 * 트리와 달리 사이클이 있어도 되고, 계층도 없습니다.
 * 친구 관계, 도로망, 인터넷 - "관계"가 있는 곳엔 그래프가 있습니다.
 *
 * 저장 방법 두 가지:
 * 1. 인접 행렬: V x V 2차원 배열. matrix[u][v] = 1이면 간선 존재
 * 2. 인접 리스트: 정점마다 "이웃 목록" 연결 리스트
 *
 * 오늘의 예제 그래프 (무방향):
 *     0 --- 1
 *     |   / |
 *     |  /  |
 *     | /   |
 *     2     3 --- 4        5 (외톨이)
 */
#include <stdio.h>
#include <stdlib.h>

#define V 6              /* 정점 수 */

/* ---------- 1. 인접 행렬 ---------- */
typedef struct {
    int matrix[V][V];
} MatrixGraph;

void mg_add_edge(MatrixGraph *g, int u, int v) {
    g->matrix[u][v] = 1;
    g->matrix[v][u] = 1;         /* 무방향: 양쪽 다 표시 */
}

int mg_has_edge(const MatrixGraph *g, int u, int v) {
    return g->matrix[u][v];      /* O(1)! */
}

void mg_print(const MatrixGraph *g) {
    printf("    ");
    for (int i = 0; i < V; i++) printf("%d ", i);
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("  %d ", i);
        for (int j = 0; j < V; j++) {
            printf("%c ", g->matrix[i][j] ? '1' : '.');
        }
        printf("\n");
    }
}

/* ---------- 2. 인접 리스트 ---------- */
typedef struct AdjNode {
    int vertex;
    struct AdjNode *next;
} AdjNode;

typedef struct {
    AdjNode *head[V];
    int edge_count;
} ListGraph;

void lg_init(ListGraph *g) {
    for (int i = 0; i < V; i++) g->head[i] = NULL;
    g->edge_count = 0;
}

void lg_add_directed(ListGraph *g, int u, int v) {
    AdjNode *node = malloc(sizeof(AdjNode));
    if (node == NULL) exit(1);
    node->vertex = v;
    node->next = g->head[u];     /* 머리 삽입 O(1) */
    g->head[u] = node;
}

void lg_add_edge(ListGraph *g, int u, int v) {
    lg_add_directed(g, u, v);
    lg_add_directed(g, v, u);    /* 무방향: 양쪽에 추가 */
    g->edge_count++;
}

int lg_has_edge(const ListGraph *g, int u, int v) {
    for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
        if (n->vertex == v) return 1;    /* 이웃 목록 순회 O(차수) */
    }
    return 0;
}

int lg_degree(const ListGraph *g, int u) {
    int d = 0;
    for (AdjNode *n = g->head[u]; n != NULL; n = n->next) d++;
    return d;
}

void lg_print(const ListGraph *g) {
    for (int i = 0; i < V; i++) {
        printf("  %d: ", i);
        for (AdjNode *n = g->head[i]; n != NULL; n = n->next) {
            printf("%d -> ", n->vertex);
        }
        printf("NULL\n");
    }
}

void lg_free(ListGraph *g) {
    for (int i = 0; i < V; i++) {
        AdjNode *n = g->head[i];
        while (n != NULL) {
            AdjNode *next = n->next;
            free(n);
            n = next;
        }
        g->head[i] = NULL;
    }
}

int main(void) {
    /* 같은 그래프를 두 방식으로 저장 */
    int edges[][2] = { {0,1}, {0,2}, {1,2}, {1,3}, {3,4} };
    int E = sizeof(edges) / sizeof(edges[0]);

    MatrixGraph mg = {{{0}}};
    ListGraph lg;
    lg_init(&lg);

    for (int i = 0; i < E; i++) {
        mg_add_edge(&mg, edges[i][0], edges[i][1]);
        lg_add_edge(&lg, edges[i][0], edges[i][1]);
    }

    printf("정점 %d개, 간선 %d개 (5번 정점은 외톨이)\n", V, E);

    printf("\n=== 인접 행렬 ===\n");
    mg_print(&mg);

    printf("\n=== 인접 리스트 ===\n");
    lg_print(&lg);

    printf("\n=== 연산 비교 ===\n");
    printf("1-2 간선 존재? 행렬: %s (O(1)), 리스트: %s (O(차수))\n",
           mg_has_edge(&mg, 1, 2) ? "예" : "아니오",
           lg_has_edge(&lg, 1, 2) ? "예" : "아니오");
    printf("정점 1의 차수(이웃 수): %d\n", lg_degree(&lg, 1));

    printf("\n=== 메모리 비교 ===\n");
    printf("행렬  : V^2 = %d칸 x %zu바이트 = %zu바이트 (간선이 적어도 고정!)\n",
           V * V, sizeof(int), (size_t)V * V * sizeof(int));
    printf("리스트: 간선당 노드 2개 = %d개 x %zu바이트 = %zu바이트\n",
           E * 2, sizeof(AdjNode), (size_t)E * 2 * sizeof(AdjNode));
    printf("\n정점 100만, 간선 300만이라면?\n");
    printf("행렬  : 10^12칸 = 4TB (불가능!)\n");
    printf("리스트: 600만 노드 = 약 100MB (거뜬)\n");

    printf("\n선택 기준:\n");
    printf("- 간선이 촘촘(밀집)하고 '연결 여부'를 자주 묻는다 -> 행렬\n");
    printf("- 간선이 성긴(희소) 현실 그래프 대부분          -> 리스트\n");
    printf("(SNS: 사용자 수십억 명, 친구는 평균 수백 명 = 초희소!)\n");

    lg_free(&lg);
    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/graph_repr.c -o build/graph_repr
$ ./build/graph_repr
정점 6개, 간선 5개 (5번 정점은 외톨이)

=== 인접 행렬 ===
    0 1 2 3 4 5
  0 . 1 1 . . .
  1 1 . 1 1 . .
  2 1 1 . . . .
  3 . 1 . . 1 .
  4 . . . 1 . .
  5 . . . . . .

=== 인접 리스트 ===
  0: 2 -> 1 -> NULL
  1: 3 -> 2 -> 0 -> NULL
  2: 1 -> 0 -> NULL
  3: 4 -> 1 -> NULL
  4: 3 -> NULL
  5: NULL

=== 연산 비교 ===
1-2 간선 존재? 행렬: 예 (O(1)), 리스트: 예 (O(차수))
정점 1의 차수(이웃 수): 3

=== 메모리 비교 ===
행렬  : V^2 = 36칸 x 4바이트 = 144바이트 (간선이 적어도 고정!)
리스트: 간선당 노드 2개 = 10개 x 16바이트 = 160바이트

정점 100만, 간선 300만이라면?
행렬  : 10^12칸 = 4TB (불가능!)
리스트: 600만 노드 = 약 100MB (거뜬)

선택 기준:
- 간선이 촘촘(밀집)하고 '연결 여부'를 자주 묻는다 -> 행렬
- 간선이 성긴(희소) 현실 그래프 대부분          -> 리스트
(SNS: 사용자 수십억 명, 친구는 평균 수백 명 = 초희소!)

인접 행렬 vs 인접 리스트

2.2 코드 한 줄씩 읽기

행렬 쪽은 배열 하나가 전부입니다.

typedef struct {
    int matrix[V][V];
} MatrixGraph;

int 36개짜리 2차원 배열을 구조체로 감쌌습니다. 굳이 구조체로 감싼 이유는 함수에 넘길 때 MatrixGraph * 한 개로 깔끔하게 넘기고, 나중에 필드를 더 붙이기 쉽게 하려는 것입니다. 8주차에서 배운 습관입니다.

    MatrixGraph mg = {{{0}}};

중괄호가 세 겹인 것이 낯설 겁니다. 바깥부터 구조체, matrix 배열, matrix[0] 행입니다. 첫 원소를 0으로 주면 나머지도 전부 0이 된다는 4주차의 배열 초기화 규칙이 3단으로 적용된 것입니다. 이 한 줄이 “간선이 하나도 없는 그래프”를 만듭니다.

리스트 쪽은 10주차 연결 리스트 그대로입니다.

typedef struct AdjNode {
    int vertex;
    struct AdjNode *next;
} AdjNode;

typedef struct {
    AdjNode *head[V];
    int edge_count;
} ListGraph;

head[V] 는 포인터 V개짜리 배열입니다. head[3] 은 “3번 정점의 이웃 목록”의 첫 노드를 가리킵니다. 노드 하나는 int 4바이트와 포인터 8바이트인데, 8주차에서 배운 정렬 규칙 때문에 sizeof(AdjNode) 는 12가 아니라 16입니다. 실행 결과의 “16바이트”가 그것입니다.

무방향 간선은 양쪽에 넣습니다. 두 구현 모두에서 이것이 핵심입니다.

void mg_add_edge(MatrixGraph *g, int u, int v) {
    g->matrix[u][v] = 1;
    g->matrix[v][u] = 1;         /* 무방향: 양쪽 다 표시 */
}

void lg_add_edge(ListGraph *g, int u, int v) {
    lg_add_directed(g, u, v);
    lg_add_directed(g, v, u);    /* 무방향: 양쪽에 추가 */
    g->edge_count++;
}

한쪽만 넣는 것이 이번 주 최다 빈출 버그입니다. 실제로 어떻게 되는지 곧 실험합니다. 방향 그래프를 만들 때는 반대로 lg_add_directed 만 쓰면 됩니다. 함수를 둘로 나눠 둔 이유입니다.

인접 리스트는 머리 삽입을 씁니다.

    node->next = g->head[u];     /* 머리 삽입 O(1) */
    g->head[u] = node;

10주차에서 배운 그대로입니다. 새 노드가 항상 맨 앞에 끼어들기 때문에, 출력 순서가 삽입 순서의 역순이 됩니다. 실행 결과에서 1: 3 -> 2 -> 0 인데 실제 삽입 순서는 0, 2, 3이었습니다. 이번 주 내내 탐색 결과의 순서가 “예상과 다르게” 나오는 이유가 대개 이것이니 기억해 두세요.

해제도 잊지 않습니다.

void lg_free(ListGraph *g) {
    for (int i = 0; i < V; i++) {
        AdjNode *n = g->head[i];
        while (n != NULL) {
            AdjNode *next = n->next;
            free(n);
            n = next;
        }
        g->head[i] = NULL;
    }
}

10주차에서 배운 “다음을 먼저 기억하고 지운다” 패턴입니다. 정점마다 목록이 하나씩 있으니 V개의 리스트를 차례로 비웁니다. 이 함수를 빼먹으면 간선 5개짜리 그래프에서도 노드 10개, 160바이트가 샙니다. 이번 주 예제는 전부 valgrind 로 누수 0을 확인했습니다.

2.3 실험: 메모리는 정말 얼마나 드나

실험 프로그램에 대해: 이 절부터 나오는 ./mem_rss, ./deep_dfs, ./floyd_wrong3 같은 짧은 실험 프로그램은 저장소의 examples/, projects/ 에 들어 있지 않습니다. 글을 쓰면서 그때그때 만들어 돌린 것이라, 본문의 설명(무엇을 어떻게 재는지)을 보고 직접 만들어 보거나 결과만 참고하면 됩니다. ./build/... 로 시작하는 명령만 저장소의 예제입니다.

프로그램은 “600만 노드 = 약 100MB” 라고 출력합니다. 16바이트 × 600만 = 9,600만 바이트니까 계산은 맞습니다. 그런데 정말 100MB 만 쓸까요? 10주차에서 malloc 으로 16바이트를 달라고 하면 실제로는 32바이트를 차지한다고 배웠습니다. 확인해 봅시다. 노드 600만 개를 malloc 하고, 리눅스가 알려 주는 실제 메모리 사용량(/proc/self/status 의 VmRSS)을 앞뒤로 비교하는 실험입니다.

$ ./mem_rss
노드 크기 sizeof(AdjNode) = 16바이트
계산상: 6000000개 x 16바이트 = 96 MB
실제 RSS 증가: 187 MB

계산의 거의 두 배인 187MB 입니다. malloc 이 노드마다 관리용 8바이트를 붙이고 16바이트 단위로 올림하기 때문입니다. 그래도 4TB 와는 비교가 안 되니 결론은 그대로입니다. “리스트가 훨씬 작다”는 것은 맞지만, 정확한 크기를 알려면 이렇게 재 봐야 합니다.

2.4 실험: 시간은 어느 쪽이 빠른가

정점 5,000개, 간선 15,000개짜리 무작위 희소 그래프를 두 방식으로 만들고 두 가지 작업의 시간을 쟀습니다. 행렬은 unsigned char 로 만들어 칸당 1바이트만 쓰도록 했습니다.

$ ./mem_time
V=5000, E=15000 (희소: 가능한 간선 12497500개 중 0.12%)
메모리  행렬: 25000000바이트 (25.0 MB)   리스트: 480000바이트 (0.48 MB)
모든 정점의 이웃 순회 x10   행렬: 117.1 ms   리스트: 1.1 ms  (검사 횟수 25000000 vs 30000)
무작위 쌍 '연결됐나?' x100만  행렬: 10.3 ms   리스트: 56.1 ms

작업	인접 행렬	인접 리스트	이유
메모리	25 MB	0.48 MB	행렬은 간선이 없어도 V² 칸
모든 정점의 이웃 순회	117 ms	1.1 ms	행렬은 빈칸 2,500만 개를 전부 확인
“u와 v가 연결됐나?” 100만 번	10 ms	56 ms	행렬은 칸 하나만 보면 끝, 리스트는 목록을 훑어야 함

같은 그래프인데 작업에 따라 승자가 바뀝니다. 이웃을 돌아다니는 작업(이번 주 알고리즘의 대부분)은 리스트가 100배 빠르고, “연결됐나?” 한 가지 질문만 반복하는 작업은 행렬이 5배 빠릅니다. 메모리는 리스트가 50배 작습니다.

여기서 희소(sparse) 와 밀집(dense) 이라는 개념이 나옵니다. 가능한 최대 간선 수는 V(V − 1)/2 인데, 실제 간선이 그보다 훨씬 적으면 희소 그래프입니다. 위 실험의 그래프는 가능한 간선의 0.12% 만 있는 초희소 그래프입니다. 그리고 현실의 그래프는 거의 다 희소합니다. 페이스북 사용자는 수십억 명이지만 평균 친구는 수백 명이고, 도시가 수천 개여도 각 도시에 연결된 도로는 수십 개입니다.

그래서 기본값은 인접 리스트입니다. 행렬을 쓰는 경우는 두 가지뿐입니다. 정점 수가 적고 촘촘할 때, 그리고 8절 플로이드-워셜처럼 행렬 자체가 알고리즘의 일부인 경우입니다.

	인접 행렬	인접 리스트
“u-v 연결됐나?”	O(1)	O(차수)
u의 이웃 전체 순회	O(V) (빈칸도 확인)	O(차수)
간선 추가	O(1)	O(1)
메모리	V²	V + 2E (차수의 합이 2E 이므로)
구현 난이도	쉬움	중간 (해제 필요)

메모리 칸의 “V + 2E” 는 1절에서 본 차수의 성질입니다. 무방향 간선 하나가 노드 두 개를 만드니 노드는 2E개, 거기에 head 배열 V개가 더해집니다.

이번 주 예제들은 상황에 따라 둘을 섞어 씁니다. DFS와 BFS는 리스트로, 다익스트라와 프림은 행렬로, 벨만-포드와 크루스칼은 아예 간선 목록(Edge 배열)으로요. 알고리즘마다 편한 표현이 다르다는 것도 같이 익혀 두세요.

2.5 실험: 무방향 간선을 한쪽만 넣으면

“양쪽에 넣어야 한다”는 말을 백 번 듣는 것보다 한 번 틀려 보는 게 낫습니다. add_directed 만 써서 0→1, 1→2, 2→3 을 넣고, 0에서 출발하는 탐색과 3에서 출발하는 탐색을 돌려 봤습니다(탐색 함수는 3절에서 배우는 DFS 입니다).

$ ./one_way
0에서 출발: 0 1 2 3
3에서 출발: 3

0에서는 네 정점을 다 만나는데, 3에서는 자기 자신밖에 못 갑니다. 간선이 한 방향으로만 저장되어 있으니 3의 이웃 목록이 비어 있기 때문입니다. 무서운 점은 오류가 나지 않는다는 것입니다. 컴파일도 되고, 실행도 되고, 결과도 그럴듯합니다. 출발점에 따라 결과가 반쪽만 나오는 버그는, 그래프가 크면 “왜 이 정점만 빠지지?” 하면서 한참을 헤매게 만듭니다. 탐색 결과가 이상하면 add_edge 부터 의심하세요.

2.6 실험: 초기화를 빼면

graph_dfs.c (다음 절)의 Graph g = {{0}}; 에서 = {{0}} 을 지우고 Graph g; 로 바꿔 컴파일해 봤습니다. 경고 하나 없이 컴파일됩니다.

$ ./dfs_noinit
세그멘테이션 오류 (코어 덤프됨)

실행하자마자 죽습니다(종료 코드 139). head[] 배열이 초기화되지 않아 쓰레기 주소를 담고 있고, add_edge 가 node->next = g->head[u] 로 그 쓰레기를 복사한 뒤 탐색이 그 주소를 따라가다 죽는 것입니다. 1주차 10절의 “초기화하지 않은 변수” 경고는 지역 변수 하나에는 뜨지만, 구조체 안의 배열까지는 컴파일러가 추적하지 못합니다. 그래프 구조체는 반드시 {{0}} 또는 memset 으로 비우고 시작하세요. 5절의 topo_sort.c 가 memset(&g, 0, sizeof(g)) 를 쓰는 것이 같은 이유입니다.

3. 깊이 우선 탐색(DFS)

3.1 트리 순회와 결정적으로 다른 점

DFS(Depth-First Search)는 한 방향으로 끝까지 파고들다가 막히면 되돌아오는(백트래킹) 탐색입니다. 12주차 트리의 전위 순회와 원리가 같습니다. “나를 방문하고, 자식들을 차례로 방문한다.”

단 하나, 결정적인 차이가 있습니다. 그래프에는 사이클이 있습니다.

0 --- 1
|   / |
|  /  |
2 --- 3      0 -> 1 -> 3 -> 2 -> 0 -> 1 -> ... 끝이 없다!

트리에서는 자식에서 부모로 돌아가는 간선이 없으니 순회가 저절로 끝났습니다. 그래프에서는 그 보장이 없습니다. 그래서 “이미 갔던 곳”을 기록하는 visited[] 배열이 필수입니다. 트리 순회 코드를 그래프에 그대로 복사하면 안 되는 이유이고, 이번 절 끝에서 정말로 복사해 보고 무슨 일이 생기는지 확인합니다.

examples/graph_dfs.c:

/*
 * graph_dfs.c - 깊이 우선 탐색(DFS)과 연결 성분
 * 14주차: 그래프 자료구조와 탐색
 *
 * DFS: 한 방향으로 끝까지 파고들다가 막히면 되돌아온다(백트래킹).
 * 12주차 트리의 전위 순회와 같은 원리인데, 그래프엔 사이클이 있으니
 * "방문 표시(visited)"가 필수입니다. 없으면 무한 루프!
 *
 * 응용: 연결 성분 찾기 - 서로 이어진 정점들의 "섬"을 구분한다.
 */
#include <stdio.h>
#include <stdlib.h>

#define V 8

typedef struct AdjNode {
    int vertex;
    struct AdjNode *next;
} AdjNode;

typedef struct {
    AdjNode *head[V];
} Graph;

void add_edge(Graph *g, int u, int v) {
    AdjNode *a = malloc(sizeof(AdjNode));
    AdjNode *b = malloc(sizeof(AdjNode));
    if (a == NULL || b == NULL) exit(1);
    a->vertex = v; a->next = g->head[u]; g->head[u] = a;
    b->vertex = u; b->next = g->head[v]; g->head[v] = b;
}

/* ---------- 재귀 DFS (함수 호출 스택 이용) ---------- */
void dfs_recursive(const Graph *g, int u, int visited[]) {
    visited[u] = 1;
    printf("%d ", u);

    for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
        if (!visited[n->vertex]) {
            dfs_recursive(g, n->vertex, visited);
        }
    }
}

/* ---------- 반복문 DFS (명시적 스택, 11-12주차 기법) ---------- */
void dfs_iterative(const Graph *g, int start) {
    int visited[V] = {0};
    int stack[V * V];            /* 넉넉하게 (중복 push 허용 방식) */
    int top = -1;

    stack[++top] = start;

    while (top >= 0) {
        int u = stack[top--];
        if (visited[u]) continue;        /* pop했는데 이미 방문 = 건너뜀 */
        visited[u] = 1;
        printf("%d ", u);

        for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
            if (!visited[n->vertex]) {
                stack[++top] = n->vertex;
            }
        }
    }
}

/* ---------- 응용: 연결 성분 ----------
 * 아직 방문 안 한 정점에서 DFS를 시작할 때마다 새 "섬" 발견 */
int find_components(const Graph *g, int component[]) {
    int visited[V] = {0};
    int count = 0;

    for (int start = 0; start < V; start++) {
        if (visited[start]) continue;

        /* start에서 닿는 모든 정점에 같은 성분 번호를 매긴다 */
        count++;
        int stack[V * V];
        int top = -1;
        stack[++top] = start;

        while (top >= 0) {
            int u = stack[top--];
            if (visited[u]) continue;
            visited[u] = 1;
            component[u] = count;
            for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
                if (!visited[n->vertex]) stack[++top] = n->vertex;
            }
        }
    }
    return count;
}

/* 경로 존재 확인: DFS가 닿으면 연결된 것 */
int has_path(const Graph *g, int from, int to) {
    int comp[V];
    find_components(g, comp);
    return comp[from] == comp[to];
}

void graph_free(Graph *g) {
    for (int i = 0; i < V; i++) {
        AdjNode *n = g->head[i];
        while (n != NULL) {
            AdjNode *next = n->next;
            free(n);
            n = next;
        }
    }
}

int main(void) {
    /* 섬이 3개인 그래프:
     *   {0,1,2,3}: 0-1, 0-2, 1-3, 2-3 (사이클 있음!)
     *   {4,5,6}  : 4-5, 5-6
     *   {7}      : 외톨이
     */
    Graph g = {{0}};
    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 3);
    add_edge(&g, 2, 3);
    add_edge(&g, 4, 5);
    add_edge(&g, 5, 6);

    printf("=== DFS: 0에서 출발 ===\n");
    int visited[V] = {0};
    printf("재귀   : ");
    dfs_recursive(&g, 0, visited);
    printf("\n반복문 : ");
    dfs_iterative(&g, 0);
    printf("\n(순서는 달라도 둘 다 {0,1,2,3}만 방문 - 4,5,6,7엔 못 간다)\n");

    printf("\nvisited 배열이 없다면? 0->1->3->2->0->1->... 무한 루프!\n");
    printf("트리와 그래프 DFS의 결정적 차이가 이것입니다.\n");

    printf("\n=== 연결 성분 (섬 찾기) ===\n");
    int comp[V];
    int count = find_components(&g, comp);
    printf("섬의 개수: %d\n", count);
    for (int c = 1; c <= count; c++) {
        printf("  섬 %d: { ", c);
        for (int i = 0; i < V; i++) {
            if (comp[i] == c) printf("%d ", i);
        }
        printf("}\n");
    }

    printf("\n=== 경로 존재 확인 ===\n");
    printf("0 -> 3 갈 수 있나? %s (같은 섬)\n",
           has_path(&g, 0, 3) ? "예" : "아니오");
    printf("0 -> 6 갈 수 있나? %s (다른 섬)\n",
           has_path(&g, 0, 6) ? "예" : "아니오");

    graph_free(&g);
    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/graph_dfs.c -o build/graph_dfs
$ ./build/graph_dfs
=== DFS: 0에서 출발 ===
재귀   : 0 2 3 1
반복문 : 0 1 3 2
(순서는 달라도 둘 다 {0,1,2,3}만 방문 - 4,5,6,7엔 못 간다)

visited 배열이 없다면? 0->1->3->2->0->1->... 무한 루프!
트리와 그래프 DFS의 결정적 차이가 이것입니다.

=== 연결 성분 (섬 찾기) ===
섬의 개수: 3
  섬 1: { 0 1 2 3 }
  섬 2: { 4 5 6 }
  섬 3: { 7 }

=== 경로 존재 확인 ===
0 -> 3 갈 수 있나? 예 (같은 섬)
0 -> 6 갈 수 있나? 아니오 (다른 섬)

3.2 재귀 DFS 를 한 단계씩 따라가기

void dfs_recursive(const Graph *g, int u, int visited[]) {
    visited[u] = 1;              /* 도장부터 찍고 */
    printf("%d ", u);

    for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
        if (!visited[n->vertex]) {
            dfs_recursive(g, n->vertex, visited);
        }
    }
}

단 여섯 줄입니다. 순서가 중요합니다.

1. 도장부터 찍습니다. 방문 표시를 먼저 하지 않고 이웃을 먼저 돌면, 이웃이 나를 다시 방문하려 들어 무한 재귀에 빠집니다.
2. 이웃을 하나씩 보며, 아직 방문 안 한 이웃만 재귀 호출합니다.
3. 이웃을 다 돌면 함수가 끝나며 호출한 곳으로 되돌아갑니다. 이것이 백트래킹입니다.

말로만 들으면 “0 2 3 1” 이라는 순서가 왜 나오는지 잘 안 보입니다. 재귀 호출이 들어가고 나오는 과정을 찍어 보면 이렇습니다(들여쓰기가 재귀 깊이입니다). 이 실험용 코드는 원본 dfs_recursive 에 출력문만 더한 것입니다.

$ ./dfs_trace
인접 리스트:
  0: 2 1
  1: 3 0
  2: 3 0
  3: 2 1
  ...

=== 재귀 DFS 추적 ===
0 방문 (깊이 0) 이웃 목록: 2 1
    2 방문 (깊이 1) 이웃 목록: 3 0(이미)
        3 방문 (깊이 2) 이웃 목록: 2(이미) 1
            1 방문 (깊이 3) 이웃 목록: 3(이미) 0(이미)
        3 로 되돌아옴
    2 로 되돌아옴
0 로 되돌아옴

읽어 봅시다.

• 0의 이웃 목록은 2 1 입니다. 머리 삽입 때문에 나중에 넣은 2가 앞에 있습니다(2.2절). 그래서 1이 아니라 2로 먼저 갑니다.
• 2의 이웃은 3 0 인데 0은 이미 도장이 찍혀 있으니 3으로 갑니다.
• 3의 이웃 2 1 중 2는 이미 방문, 1은 아직이라 1로 갑니다.
• 1의 이웃 3 0 은 둘 다 방문 완료. 더 갈 곳이 없으니 되돌아옵니다. 3으로, 2로, 0으로 차례로 돌아오며 각 정점의 남은 이웃을 확인하지만 전부 방문 완료라 그대로 끝납니다.

방문 순서 0 2 3 1 은 이렇게 나왔습니다. 그리고 4, 5, 6, 7 은 0에서 간선으로 닿지 않으니 한 번도 등장하지 않습니다.

여기서 스택은 어디에 있을까요? 함수 호출 스택이 곧 DFS의 스택입니다. “3으로 되돌아옴”이 가능한 것은, 3을 처리하던 dfs_recursive 호출이 5주차에서 배운 호출 스택에 그대로 남아 있다가 1의 처리가 끝나면 이어서 실행되기 때문입니다. 우리가 스택을 만들지 않았을 뿐, 되돌아갈 위치를 기억하는 일은 CPU가 대신 해 주고 있습니다.

3.3 반복문 DFS: 스택을 직접 들고

11주차에서 “재귀는 스택이다”라고 배웠습니다. 그 약속을 여기서 지킵니다.

void dfs_iterative(const Graph *g, int start) {
    int visited[V] = {0};
    int stack[V * V];            /* 넉넉하게 (중복 push 허용 방식) */
    int top = -1;

    stack[++top] = start;

    while (top >= 0) {
        int u = stack[top--];
        if (visited[u]) continue;        /* pop했는데 이미 방문 = 건너뜀 */
        visited[u] = 1;
        printf("%d ", u);

        for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
            if (!visited[n->vertex]) {
                stack[++top] = n->vertex;
            }
        }
    }
}

11주차 배열 스택 그대로입니다. stack[++top] = x 가 push, stack[top--] 가 pop 입니다. 같은 그래프에서 스택의 내용이 어떻게 변하는지 단계별로 찍어 봤습니다.

=== 반복문 DFS 추적 ===
단계  꺼낸 정점  처리        스택(바닥→꼭대기)
  1   0         방문, push: 2 1  [2 1]
  2   1         방문, push: 3    [2 3]
  3   3         방문, push: 2    [2 2]
  4   2         방문, push: (없음) [2]
  5   2         이미 방문, 버림 []

단계	무슨 일이	왜
1	0을 꺼내 방문. 이웃 2, 1을 순서대로 push	스택은 [2 1], 꼭대기가 1
2	1을 꺼냅니다 (마지막에 넣은 것이 먼저 나오므로). 이웃 중 미방문인 3을 push	재귀 버전은 2로 먼저 갔는데, 반복문은 1로 먼저 갑니다
3	3을 꺼내 방문. 이웃 2가 아직 미방문이라 push	스택에 2가 두 개 들어 있습니다
4	2를 꺼내 방문. 이웃 3, 0은 모두 방문 완료	push 할 것이 없습니다
5	남은 2를 꺼냈는데 이미 방문	if (visited[u]) continue; 가 버립니다

주목할 점 두 가지입니다.

중복 push를 허용합니다. 3단계에서 2가 스택에 두 번 들어갔습니다. “아직 방문하지 않은 이웃”을 무조건 넣기 때문에, 같은 정점이 여러 경로에서 push 될 수 있습니다. 그래서 pop 한 뒤에 if (visited[u]) continue; 로 걸러냅니다. 스택 크기를 V * V 로 넉넉히 잡은 이유도 이것입니다. 이 “일단 넣고 꺼낼 때 거른다”는 방식은 뒤에서 볼 힙 기반 다익스트라에서도 똑같이 쓰이며, 지연 삭제(lazy deletion) 라고 부릅니다.

방문 순서가 재귀 버전과 다릅니다. 재귀는 0 2 3 1, 반복문은 0 1 3 2 입니다. 재귀는 이웃 목록의 앞 원소를 먼저 파고들고, 반복문은 이웃을 전부 push 한 뒤 마지막 원소부터 꺼내기 때문입니다. 둘 다 올바른 DFS입니다. DFS의 방문 순서는 하나로 정해져 있지 않습니다. 이웃을 어떤 순서로 보느냐에 따라 달라집니다. “정답 순서”가 있다고 오해하면 디버깅할 때 헛수고를 하게 됩니다.

3.4 실험: visited 를 빼면 정말 무한 루프인가

프로그램이 “무한 루프!” 라고 경고만 하고 넘어갔으니 직접 해 봅시다. 정점 네 개를 사각형(0-1-2-3-0)으로 잇고, dfs_recursive 에서 visited 검사를 지운 함수를 돌렸습니다.

void dfs_bad(int u) {
    printf("%d ", u);
    for (AdjNode *n = head[u]; n != NULL; n = n->next)
        dfs_bad(n->vertex);              /* visited 검사가 없다 */
}

$ ./dfs_novisited
0 3 0 3 0 3 0 3 ...
세그멘테이션 오류 (코어 덤프됨)
$ echo $?
139

0 3 0 3 ... 을 반복하다가 죽습니다. 0의 첫 이웃이 3(머리 삽입으로 마지막에 넣은 간선), 3의 첫 이웃이 0이라 둘 사이를 영원히 오갑니다. 그런데 왜 “무한 루프”가 아니라 세그멘테이션 오류로 끝날까요? 재귀 호출이 끝나지 않으니 5주차에서 본 것처럼 호출 스택이 계속 쌓이고, 8MB 스택을 다 쓰는 순간 터집니다. 재귀로 만든 무한 루프는 이렇게 죽습니다.

반복문 버전에서 visited 를 빼면 어떻게 될까요? 스택 배열 stack[V * V] 에 정점이 끝없이 push 되어 배열 범위를 넘어가고, 역시 세그멘테이션 오류가 납니다. 4주차에서 본 배열 범위 초과입니다. 어느 쪽이든 visited 없는 그래프 탐색은 반드시 죽습니다. 사이클이 하나만 있어도요.

3.5 실험: 재귀 DFS 는 얼마나 깊이 갈 수 있나

재귀 DFS에는 또 하나의 한계가 있습니다. 정점이 한 줄로 늘어선 그래프(0-1-2-…-N)를 만들고, 0에서 재귀 DFS를 돌리면 재귀 깊이가 N이 됩니다. N을 늘려 봤습니다.

$ ./deep_dfs 10000 r
재귀   : 정점 10000개, 최대 깊이 10000 - 완료
$ ./deep_dfs 100000 r
재귀   : 정점 100000개, 최대 깊이 100000 - 완료
$ ./deep_dfs 1000000 r
세그멘테이션 오류 (코어 덤프됨)
$ ./deep_dfs 1000000 i
반복문 : 정점 1000000개 방문 - 완료

정점 10만 개까지는 되고, 100만 개에서 재귀만 죽습니다. 어디쯤에서 죽는지 5만 단위로 찍어 보면 25만을 지나 죽습니다.

$ ./deep_probe 1000000
  깊이 0 도달
  깊이 50000 도달
  ...
  깊이 250000 도달
세그멘테이션 오류 (코어 덤프됨)

계산이 맞는지 확인해 봅시다. 이 함수 하나가 호출될 때 스택에 쌓이는 크기는 되돌아갈 주소 8바이트, 저장해 둘 이전 프레임 주소 8바이트, 지역 변수 자리 16바이트로 32바이트입니다(gcc -S 로 어셈블리를 보면 subq $16, %rsp 가 있습니다). ulimit -s 로 확인한 스택 한도는 8192KB 이고, 8 × 1024 × 1024 ÷ 32 = 262,144 입니다. 25만을 조금 넘긴 곳에서 죽은 실측과 맞습니다. 실제 프로그램의 함수는 지역 변수가 더 많아 프레임이 더 크니, 한계는 이보다 낮습니다.

그래서 정점이 수십만 개를 넘을 수 있는 그래프에는 반복문 DFS를 씁니다. 반복문 버전의 스택은 힙에 malloc 으로 잡을 수 있어서 8MB 한도가 없습니다. 예제가 굳이 두 버전을 모두 실은 이유입니다.

3.6 DFS의 대표 응용: 연결 성분

DFS의 가장 쓸모 있는 응용은 연결 성분(connected component) 찾기입니다. 서로 닿을 수 있는 정점들의 덩어리, 쉽게 말해 “섬”을 구분하는 것입니다.

    for (int start = 0; start < V; start++) {
        if (visited[start]) continue;

        count++;          /* 새 섬 발견! */
        ... start에서 닿는 모든 정점에 component[] = count 를 매긴다 ...
    }

아이디어가 우아합니다. 모든 정점을 순서대로 보다가, 아직 방문 안 한 정점을 만나면 그때가 새로운 섬을 발견한 순간입니다. 거기서 DFS를 시작해 닿는 모든 정점에 같은 번호를 매기면 그 섬 전체가 처리됩니다. 바깥 루프로 돌아왔을 때 아직 방문 안 한 정점이 남아 있다면, 그것은 앞의 섬에서 닿을 수 없는 곳, 즉 또 다른 섬입니다.

실행 결과를 다시 보세요. start = 0 에서 섬 1 {0 1 2 3} 이 전부 표시되고, 1, 2, 3은 이미 방문이라 건너뛰고, start = 4 에서 섬 2 {4 5 6}, start = 7 에서 섬 3 {7} 이 발견됩니다. 바깥 루프는 V번 돌지만 DFS는 섬 수만큼만 시작되고, 각 정점은 정확히 한 번 방문되니 전체가 O(V + E) 입니다.

이 기법 하나로 다양한 문제가 풀립니다.

• SNS에서 완전히 분리된 커뮤니티 찾기 (프로젝트 2에서 씁니다)
• 그림판의 “페인트통 채우기” (같은 색으로 이어진 픽셀이 곧 연결 성분입니다)
• 네트워크가 두 동강 났는지 확인하기
• 미로에서 출구에 도달할 수 있는지 판정하기

그리고 has_path 처럼 “두 정점이 연결되었나?”라는 질문도 성분 번호 비교 한 번으로 끝납니다.

int has_path(const Graph *g, int from, int to) {
    int comp[V];
    find_components(g, comp);
    return comp[from] == comp[to];
}

다만 이 구현은 호출할 때마다 전체 그래프를 다시 훑습니다. 연결 여부를 자주 물어야 한다면 성분 번호를 한 번만 계산해 두고 재사용하거나, 9절에서 배울 Union-Find 를 쓰는 편이 훨씬 빠릅니다.

4. 너비 우선 탐색(BFS)

4.1 물결처럼 퍼지기

BFS(Breadth-First Search)는 가까운 곳부터 물결처럼 퍼져 나가는 탐색입니다. 도구는 11주차의 큐이고, 12주차 트리의 레벨 순서 순회와 원리가 같습니다.

출발점에서
  거리 0: 0
  거리 1: 1, 4          <- 먼저 이 층을 전부
  거리 2: 2, 5          <- 그 다음 이 층을 전부
  거리 3: 3, 6
  거리 4: 7

그리고 BFS에는 보물 같은 성질이 있습니다.

가중치 없는 그래프에서, BFS가 정점에 처음 도착한 경로가 곧 최단 경로다.

가까운 층부터 빠짐없이 훑으니 당연한 이야기인데, 이 당연함이 강력합니다. “몇 다리 건너면 아는 사람인가”, “최소 몇 번 환승하면 되는가”, “미로의 최단 탈출로는” 같은 질문이 전부 BFS 한 번으로 풀립니다.

examples/graph_bfs.c:

/*
 * graph_bfs.c - 너비 우선 탐색(BFS)과 최단 경로(간선 수 기준)
 * 14주차: 그래프 자료구조와 탐색
 *
 * BFS: 가까운 곳부터 물결처럼 퍼져나간다. 도구는 큐(11주차)!
 * 12주차 트리의 레벨 순서 순회와 같은 원리입니다.
 *
 * BFS의 보물 같은 성질:
 *   가중치 없는 그래프에서 BFS가 정점에 "처음 도착한 경로"가 곧
 *   최단 경로다! (가까운 층부터 훑으니까 당연하지만 강력하다)
 *
 * parent 배열로 경로까지 복원합니다.
 */
#include <stdio.h>
#include <stdlib.h>

#define V 8

typedef struct AdjNode {
    int vertex;
    struct AdjNode *next;
} AdjNode;

typedef struct {
    AdjNode *head[V];
} Graph;

void add_edge(Graph *g, int u, int v) {
    AdjNode *a = malloc(sizeof(AdjNode));
    AdjNode *b = malloc(sizeof(AdjNode));
    if (a == NULL || b == NULL) exit(1);
    a->vertex = v; a->next = g->head[u]; g->head[u] = a;
    b->vertex = u; b->next = g->head[v]; g->head[v] = b;
}

/* BFS: dist[](출발점에서의 거리)와 parent[](직전 정점)를 채운다 */
void bfs(const Graph *g, int start, int dist[], int parent[]) {
    int visited[V] = {0};
    int queue[V];                /* 각 정점은 한 번만 들어가니 V면 충분 */
    int front = 0, rear = 0;

    for (int i = 0; i < V; i++) {
        dist[i] = -1;            /* -1 = 도달 불가 */
        parent[i] = -1;
    }

    visited[start] = 1;
    dist[start] = 0;
    queue[rear++] = start;

    while (front < rear) {
        int u = queue[front++];  /* dequeue */

        for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
            int v = n->vertex;
            if (!visited[v]) {
                visited[v] = 1;          /* enqueue할 때 표시! (중복 방지) */
                dist[v] = dist[u] + 1;   /* 한 층 더 멀다 */
                parent[v] = u;           /* 어디서 왔는지 기록 */
                queue[rear++] = v;
            }
        }
    }
}

/* parent를 거슬러 올라가 경로 출력 (재귀로 순서 뒤집기) */
void print_path(const int parent[], int v) {
    if (parent[v] == -1) {
        printf("%d", v);
        return;
    }
    print_path(parent, parent[v]);
    printf(" -> %d", v);
}

void graph_free(Graph *g) {
    for (int i = 0; i < V; i++) {
        AdjNode *n = g->head[i];
        while (n != NULL) {
            AdjNode *next = n->next;
            free(n);
            n = next;
        }
    }
}

int main(void) {
    /* 지하철 노선 같은 그래프:
     *
     *   0 -- 1 -- 2 -- 3
     *   |         |
     *   4 -- 5 -- 6 -- 7
     *
     * 0에서 3까지: 위로 가면 3정거장, 아래로 돌면 5정거장
     */
    Graph g = {{0}};
    add_edge(&g, 0, 1);
    add_edge(&g, 1, 2);
    add_edge(&g, 2, 3);
    add_edge(&g, 0, 4);
    add_edge(&g, 4, 5);
    add_edge(&g, 5, 6);
    add_edge(&g, 2, 6);
    add_edge(&g, 6, 7);

    int dist[V], parent[V];
    bfs(&g, 0, dist, parent);

    printf("=== BFS: 0번 역에서 출발 ===\n\n");
    printf("정점  거리  최단 경로\n");
    printf("---------------------------\n");
    for (int i = 0; i < V; i++) {
        printf("  %d    %2d   ", i, dist[i]);
        if (dist[i] >= 0) print_path(parent, i);
        else              printf("(도달 불가)");
        printf("\n");
    }

    printf("\n주목: 7번까지 두 경로가 있다\n");
    printf("  0->1->2->6->7 (4정거장) vs 0->4->5->6->7 (4정거장)\n");
    printf("  BFS는 둘 중 하나를 찾는다 (같은 길이면 어느 쪽이든 최단!)\n");

    printf("\nBFS vs DFS 한 줄 정리:\n");
    printf("  BFS(큐)  : 가까운 곳부터. '최단 경로', '몇 다리 건너'\n");
    printf("  DFS(스택): 한 우물 끝까지. '경로 존재', '사이클', '백트래킹'\n");

    printf("\n핵심 디테일: visited 표시는 큐에 '넣을 때' 한다.\n");
    printf("꺼낼 때 하면 같은 정점이 큐에 여러 번 들어가 비효율!\n");

    graph_free(&g);
    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/graph_bfs.c -o build/graph_bfs
$ ./build/graph_bfs
=== BFS: 0번 역에서 출발 ===

정점  거리  최단 경로
---------------------------
  0     0   0
  1     1   0 -> 1
  2     2   0 -> 1 -> 2
  3     3   0 -> 1 -> 2 -> 3
  4     1   0 -> 4
  5     2   0 -> 4 -> 5
  6     3   0 -> 4 -> 5 -> 6
  7     4   0 -> 4 -> 5 -> 6 -> 7

주목: 7번까지 두 경로가 있다
  0->1->2->6->7 (4정거장) vs 0->4->5->6->7 (4정거장)
  BFS는 둘 중 하나를 찾는다 (같은 길이면 어느 쪽이든 최단!)

BFS vs DFS 한 줄 정리:
  BFS(큐)  : 가까운 곳부터. '최단 경로', '몇 다리 건너'
  DFS(스택): 한 우물 끝까지. '경로 존재', '사이클', '백트래킹'

핵심 디테일: visited 표시는 큐에 '넣을 때' 한다.
꺼낼 때 하면 같은 정점이 큐에 여러 번 들어가 비효율!

4.2 큐를 한 단계씩 따라가기

BFS 구현의 핵심은 배열 세 개를 함께 관리하는 것입니다.

• visited[]: 이미 큐에 넣었는가
• dist[]: 출발점에서 몇 걸음인가 (-1 은 도달 불가)
• parent[]: 어느 정점에서 여기로 왔는가

    visited[start] = 1;
    dist[start] = 0;
    queue[rear++] = start;

    while (front < rear) {
        int u = queue[front++];  /* dequeue */

        for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
            int v = n->vertex;
            if (!visited[v]) {
                visited[v] = 1;          /* enqueue할 때 표시! (중복 방지) */
                dist[v] = dist[u] + 1;   /* 한 층 더 멀다 */
                parent[v] = u;           /* 어디서 왔는지 기록 */
                queue[rear++] = v;
            }
        }
    }

큐는 11주차의 배열 큐입니다. queue[rear++] = v 가 enqueue, queue[front++] 가 dequeue, front < rear 가 “비어 있지 않다”입니다. 큐의 내용이 어떻게 변하는지 단계별로 찍어 봤습니다. 괄호 안은 dist 값입니다.

$ ./bfs_trace
인접 리스트:
  0: 4 1
  1: 2 0
  2: 6 3 1
  ...

단계  꺼낸 정점(거리)  새로 넣은 정점(거리)     큐(앞→뒤)
  1   0(0)            4(1) 1(1)              [4 1]
  2   4(1)            5(2)                   [1 5]
  3   1(1)            2(2)                   [5 2]
  4   5(2)            6(3)                   [2 6]
  5   2(2)            3(3)                   [6 3]
  6   6(3)            7(4)                   [3 7]
  7   3(3)            (없음)                 [7]
  8   7(4)            (없음)                 []

표에서 눈여겨볼 것이 두 가지입니다.

거리 순으로 처리됩니다. 꺼낸 정점의 거리를 세로로 읽으면 0, 1, 1, 2, 2, 3, 3, 4 입니다. 절대 거꾸로 가지 않습니다. 큐가 선입선출이라 먼저 넣은(가까운) 정점이 먼저 나오기 때문입니다. dist[v] = dist[u] + 1 이 BFS가 최단 거리를 구하는 원리 전부입니다. u까지의 거리가 최단이고 v가 u의 이웃이면, v까지는 한 걸음 더입니다. 그리고 v를 처음 만난 순간이 가장 가까운 층에서 만난 순간이니, 그때의 거리가 최단입니다.

6은 5에서 왔습니다. 6번 정점은 2와 5 양쪽의 이웃입니다. 4단계에서 5를 처리할 때 6을 먼저 큐에 넣고 visited[6] = 1 로 표시했기 때문에, 5단계에서 2를 처리할 때는 6이 이미 표시되어 있어 건드리지 않습니다. 그래서 7까지의 경로가 0 -> 4 -> 5 -> 6 -> 7 로 나왔습니다. 0 -> 1 -> 2 -> 6 -> 7 도 같은 길이 4인데, BFS는 먼저 도착한 쪽을 기록합니다. 0의 이웃 목록이 4 1 순서라(머리 삽입!) 4쪽 물결이 반 박자 빨랐습니다.

직접 해 보기: main 에서 add_edge(&g, 0, 4) 를 add_edge(&g, 0, 1) 보다 앞에 오도록 순서를 바꿔 보세요. 0의 이웃 목록이 1 4 로 바뀌어 7까지의 경로가 0 -> 1 -> 2 -> 6 -> 7 로 달라집니다. 거리는 그대로 4입니다. 간선을 넣는 순서가 “어느 최단 경로”를 고르는지를 결정합니다.

4.3 실험: 방문 표시를 꺼낼 때 하면

이 예제가 강조하는 디테일입니다. 방문 표시를 큐에서 꺼낼 때 하면 안 됩니다. 얼마나 나빠지는지 세어 봤습니다. “넣을 때 표시”와 “꺼낼 때 표시”로 각각 BFS를 돌리며 큐에 넣은 횟수를 셌습니다.

=== 큐에 넣는 횟수 (정점 8개 지하철 그래프) ===
넣을 때 표시: 8회
꺼낼 때 표시: 9회

=== 큐에 넣는 횟수 (정점 8개가 전부 서로 연결된 그래프) ===
넣을 때 표시: 8회
꺼낼 때 표시: 29회

지하철 그래프에서는 6번 정점이 한 번 더 들어가서 9회입니다. 꺼낼 때 표시하는 방식이라면 5를 처리할 때 6을 넣고, 2를 처리할 때도 (6이 아직 안 꺼내져 미방문 상태라) 6을 또 넣기 때문입니다. 간선이 많은 그래프에서는 이 중복이 폭발합니다. 정점 8개가 전부 서로 연결된 그래프에서는 8회면 될 것을 29회 넣습니다. 정점 수가 늘면 차이는 더 커집니다.

넣을 때 표시하면 각 정점이 큐에 정확히 한 번만 들어갑니다. 그래서 int queue[V]; 처럼 큐 크기를 V로 잡아도 안전한 것입니다. DFS의 반복문 버전에서 V * V 를 잡아야 했던 것과 대조되는 부분이고, BFS가 DFS보다 큐 관리가 깔끔한 이유이기도 합니다.

4.4 경로 복원: parent 배열 거슬러 올라가기

dist 만으로는 “몇 걸음”인지만 알 뿐 “어떤 길”인지는 모릅니다. 그래서 parent[] 를 기록해 둡니다. 실행 후 parent 배열의 내용은 이렇습니다.

정점	0	1	2	3	4	5	6	7
parent	-1	0	1	2	0	4	5	6

7의 경로를 알고 싶으면 parent[7] = 6, parent[6] = 5, parent[5] = 4, parent[4] = 0, parent[0] = -1 로 따라가면 됩니다. 그런데 이렇게 하면 도착점 → 출발점 역순으로 나옵니다. 이것을 뒤집어야 하는데, 예제는 재귀로 뒤집습니다.

void print_path(const int parent[], int v) {
    if (parent[v] == -1) {       /* 출발점에 도달하면 재귀 종료 */
        printf("%d", v);
        return;
    }
    print_path(parent, parent[v]);   /* 먼저 앞쪽 경로를 출력하고 */
    printf(" -> %d", v);             /* 그 다음에 나를 출력 */
}

자기 자신을 먼저 출력하지 않고 부모를 먼저 호출하면, 재귀가 출발점까지 들어갔다가 돌아 나오면서 출력이 정순으로 찍힙니다. 5주차 재귀에서 본 “돌아 나오는 길에 일하기” 패턴입니다. parent[start] == -1 이 재귀 종료 조건이라는 점도 눈여겨보세요. 출발점만 부모가 없으니 자연스러운 기저 조건이 됩니다.

배열에 담아 뒤집는 방법도 있고(프로젝트 1의 build_route 가 그렇게 합니다), 11주차의 스택을 써도 됩니다. 셋 다 같은 일을 하는 다른 방법입니다.

4.5 BFS와 DFS, 언제 무엇을?

	BFS (큐)	DFS (스택/재귀)
탐색 순서	가까운 곳부터 층별로	한 방향 끝까지
최단 경로(무가중치)	구할 수 있다	구할 수 없다
큐/스택에 들어가는 횟수	정점당 정확히 1번	중복 가능 (걸러냄)
메모리	한 층의 정점 수만큼	경로 깊이만큼 (재귀는 8MB 한도)
대표 용도	최단 거리, 몇 다리 건너, 레벨별 처리	경로 존재, 사이클 탐지, 백트래킹, 위상 정렬
구현	큐 필수	재귀가 간편, 깊으면 반복문

한 줄로 정리하면 BFS(큐)는 “최단”이 필요할 때, DFS(스택)는 “존재/구조”가 필요할 때입니다. 둘 다 시간은 O(V + E) 로 같습니다. 각 정점을 한 번, 각 간선을 (양 끝에서) 두 번 보기 때문입니다.

메모리 특성도 실무에서 갈립니다. 넓고 얕은 그래프에서는 BFS의 큐가 커지고, 깊고 좁은 그래프에서는 3.5절에서 본 것처럼 재귀 DFS가 스택을 넘칩니다.

5. 위상 정렬: 의존성의 순서 찾기

5.1 문제

방향 그래프에서 “선행 조건을 지키는 순서”를 찾는 문제입니다. 현실에 정말 많습니다.

• 과목 선수 관계: 자료구조를 들으려면 C기초를 먼저
• 빌드 의존성: main.o 를 만들려면 main.c 와 헤더가 먼저 (5주차의 Makefile!)
• 패키지 설치: 1주차에 apt 가 gcc 를 설치하기 전에 부품 패키지부터 깔던 것
• 작업 일정: 기초 공사 후 골조, 골조 후 마감

이런 순서를 찾는 것을 위상 정렬(topological sort) 이라고 합니다. 여기서는 Kahn 알고리즘(BFS 계열)을 씁니다.

1. 각 정점의 진입 차수(들어오는 간선 수 = 선행 조건 개수)를 센다
2. 진입 차수가 0인 정점(선행 조건 없음)을 전부 큐에 넣는다
3. 하나 꺼내 결과에 추가하고, 그 정점이 막고 있던 이웃들의 진입 차수를 1씩 줄인다. 0이 되면 큐에 넣는다
4. 큐가 빌 때까지 반복

examples/topo_sort.c:

/*
 * topo_sort.c - 위상 정렬 (Kahn 알고리즘)
 * 14주차: 그래프 자료구조와 탐색
 *
 * 방향 그래프에서 "선행 조건을 지키는 순서"를 찾는 문제입니다.
 * 예: 과목 선수 관계, 빌드 의존성(Makefile!), 작업 순서.
 *
 * Kahn 알고리즘 (BFS 계열):
 * 1. 각 정점의 진입 차수(들어오는 간선 수)를 센다
 * 2. 진입 차수 0인 정점(선행 조건 없음)을 큐에 넣는다
 * 3. 하나 꺼내 결과에 추가하고, 그 정점에서 나가는 간선을 지운다
 *    (이웃의 진입 차수 감소, 0이 되면 큐에 추가)
 * 4. 반복. 결과에 V개가 안 담기면? 사이클이 있다는 증거!
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define V 8

/* 과목 이름 (정점 번호 = 인덱스) */
static const char *course[V] = {
    "C기초", "자료구조", "알고리즘", "운영체제",
    "컴퓨터구조", "시스템프로그래밍", "네트워크", "졸업프로젝트",
};

typedef struct AdjNode {
    int vertex;
    struct AdjNode *next;
} AdjNode;

typedef struct {
    AdjNode *head[V];
    int in_degree[V];
} Digraph;

/* 방향 간선: u를 들어야 v를 들을 수 있다 (u -> v) */
void add_edge(Digraph *g, int u, int v) {
    AdjNode *n = malloc(sizeof(AdjNode));
    if (n == NULL) exit(1);
    n->vertex = v;
    n->next = g->head[u];
    g->head[u] = n;
    g->in_degree[v]++;           /* v로 들어오는 간선 +1 */
}

/* 위상 정렬. 성공하면 정렬된 정점 수(V), 사이클이 있으면 그보다 작다 */
int topo_sort(Digraph *g, int order[]) {
    int in_deg[V];
    memcpy(in_deg, g->in_degree, sizeof(in_deg));   /* 원본 보존 */

    int queue[V];
    int front = 0, rear = 0;

    /* 1. 선행 조건 없는 과목들부터 */
    for (int i = 0; i < V; i++) {
        if (in_deg[i] == 0) queue[rear++] = i;
    }

    int count = 0;
    while (front < rear) {
        int u = queue[front++];
        order[count++] = u;

        /* 2. u를 이수했으니 u가 막고 있던 과목들의 조건이 하나 풀린다 */
        for (AdjNode *n = g->head[u]; n != NULL; n = n->next) {
            in_deg[n->vertex]--;
            if (in_deg[n->vertex] == 0) {
                queue[rear++] = n->vertex;
            }
        }
    }
    return count;                /* count < V 이면 사이클! */
}

void digraph_free(Digraph *g) {
    for (int i = 0; i < V; i++) {
        AdjNode *n = g->head[i];
        while (n != NULL) {
            AdjNode *next = n->next;
            free(n);
            n = next;
        }
        g->head[i] = NULL;
    }
}

int main(void) {
    Digraph g;
    memset(&g, 0, sizeof(g));

    /* 선수 관계: A -> B = "A를 먼저 들어야 B 수강 가능" */
    struct { int from, to; } prereq[] = {
        {0, 1},  /* C기초 -> 자료구조 */
        {0, 4},  /* C기초 -> 컴퓨터구조 */
        {1, 2},  /* 자료구조 -> 알고리즘 */
        {4, 3},  /* 컴퓨터구조 -> 운영체제 */
        {1, 5},  /* 자료구조 -> 시스템프로그래밍 */
        {3, 5},  /* 운영체제 -> 시스템프로그래밍 */
        {3, 6},  /* 운영체제 -> 네트워크 */
        {2, 7},  /* 알고리즘 -> 졸업프로젝트 */
        {5, 7},  /* 시스템프로그래밍 -> 졸업프로젝트 */
        {6, 7},  /* 네트워크 -> 졸업프로젝트 */
    };
    int E = sizeof(prereq) / sizeof(prereq[0]);

    printf("=== 과목 선수 관계 ===\n");
    for (int i = 0; i < E; i++) {
        add_edge(&g, prereq[i].from, prereq[i].to);
        printf("  %s -> %s\n", course[prereq[i].from], course[prereq[i].to]);
    }

    printf("\n진입 차수 (선행 과목 수):\n");
    for (int i = 0; i < V; i++) {
        printf("  %-18s %d\n", course[i], g.in_degree[i]);
    }

    int order[V];
    int count = topo_sort(&g, order);

    printf("\n=== 위상 정렬 결과: 수강 순서 ===\n");
    for (int i = 0; i < count; i++) {
        printf("%d학기: %s\n", i + 1, course[order[i]]);
    }

    /* 사이클 실험: 졸업프로젝트 -> C기초 라는 말도 안 되는 조건 추가 */
    printf("\n=== 사이클 감지 실험 ===\n");
    printf("'졸업프로젝트 -> C기초' 간선을 추가하면? (순환 조건!)\n");
    add_edge(&g, 7, 0);
    count = topo_sort(&g, order);
    printf("정렬된 과목: %d개 / %d개 -> %s\n",
           count, V,
           count < V ? "사이클 발견! 이 커리큘럼은 이수 불가능"
                     : "정상");

    printf("\n실전: make가 빌드 순서를 정하고 '순환 의존성' 에러를\n");
    printf("내는 것이 정확히 이 알고리즘입니다.\n");

    digraph_free(&g);
    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/topo_sort.c -o build/topo_sort
$ ./build/topo_sort
=== 과목 선수 관계 ===
  C기초 -> 자료구조
  C기초 -> 컴퓨터구조
  자료구조 -> 알고리즘
  컴퓨터구조 -> 운영체제
  자료구조 -> 시스템프로그래밍
  운영체제 -> 시스템프로그래밍
  운영체제 -> 네트워크
  알고리즘 -> 졸업프로젝트
  시스템프로그래밍 -> 졸업프로젝트
  네트워크 -> 졸업프로젝트

진입 차수 (선행 과목 수):
  C기초            0
  자료구조       1
  알고리즘       1
  운영체제       1
  컴퓨터구조    1
  시스템프로그래밍 2
  네트워크       1
  졸업프로젝트 3

=== 위상 정렬 결과: 수강 순서 ===
1학기: C기초
2학기: 컴퓨터구조
3학기: 자료구조
4학기: 운영체제
5학기: 알고리즘
6학기: 네트워크
7학기: 시스템프로그래밍
8학기: 졸업프로젝트

=== 사이클 감지 실험 ===
'졸업프로젝트 -> C기초' 간선을 추가하면? (순환 조건!)
정렬된 과목: 0개 / 8개 -> 사이클 발견! 이 커리큘럼은 이수 불가능

실전: make가 빌드 순서를 정하고 '순환 의존성' 에러를
내는 것이 정확히 이 알고리즘입니다.

진입 차수 표의 줄이 들쭉날쭉한 것은 %-18s 가 바이트 수로 폭을 맞추기 때문입니다. 한글은 한 글자가 3바이트라 글자 수가 많을수록 남는 칸이 줄어듭니다. 4주차와 8주차에서 본 그 문제입니다.

5.2 큐와 진입 차수를 한 단계씩 따라가기

void add_edge(Digraph *g, int u, int v) {
    ...
    g->head[u] = n;
    g->in_degree[v]++;           /* v로 들어오는 간선 +1 */
}

간선을 추가할 때 한쪽만 넣습니다. 방향 그래프니까요. 그리고 동시에 도착점의 진입 차수를 올립니다. 이렇게 해 두면 나중에 따로 셀 필요가 없습니다.

int topo_sort(Digraph *g, int order[]) {
    int in_deg[V];
    memcpy(in_deg, g->in_degree, sizeof(in_deg));   /* 원본 보존 */

진입 차수를 복사해서 씁니다. 알고리즘이 진행되며 값을 깎아 나가기 때문에, 원본을 쓰면 함수를 두 번 호출할 수 없게 됩니다. 이 예제는 사이클 실험을 위해 topo_sort 를 두 번 호출하므로 이 복사가 꼭 필요합니다. “입력을 망가뜨리지 않는다”는 것은 함수를 만들 때의 좋은 습관이기도 합니다.

핵심 루프가 진입 차수를 어떻게 깎아 나가는지 찍어 봤습니다. 괄호 안이 줄어든 뒤의 진입 차수이고, →큐 는 0이 되어 큐에 들어갔다는 표시입니다.

$ ./topo_trace
시작 큐: [C기초]

단계  꺼낸 과목        진입 차수가 줄어든 과목(새 값)          큐
  1   C기초           컴퓨터구조(0)→큐 자료구조(0)→큐        [컴퓨터구조 자료구조]
  2   컴퓨터구조      운영체제(0)→큐                          [자료구조 운영체제]
  3   자료구조        시스템프로그래밍(1) 알고리즘(0)→큐      [운영체제 알고리즘]
  4   운영체제        네트워크(0)→큐 시스템프로그래밍(0)→큐   [알고리즘 네트워크 시스템프로그래밍]
  5   알고리즘        졸업프로젝트(2)                         [네트워크 시스템프로그래밍]
  6   네트워크        졸업프로젝트(1)                         [시스템프로그래밍]
  7   시스템프로그래밍 졸업프로젝트(0)→큐                     [졸업프로젝트]
  8   졸업프로젝트    (없음)                                  []

3단계를 보세요. 자료구조를 이수하면 시스템프로그래밍의 조건이 하나 풀리지만(2 → 1), 운영체제라는 조건이 아직 남아 있어 큐에 들어가지 않습니다. 4단계에서 운영체제를 이수한 뒤에야 0이 되어 큐에 들어갑니다. “모든 선행 조건이 풀린 뒤에만 들을 수 있다”가 진입 차수 0이라는 조건으로 정확히 표현된 것입니다.

졸업프로젝트는 진입 차수 3에서 시작해 5, 6, 7단계에 하나씩 줄어 마지막에 0이 됩니다. 선행 과목 세 개가 모두 끝난 뒤에만 들을 수 있으니 8학기가 됩니다.

위상 정렬의 답은 하나가 아닙니다. 2단계에서 큐에 컴퓨터구조와 자료구조가 함께 들어 있었는데, 어느 쪽을 먼저 꺼내도 유효한 순서가 됩니다. 이 예제는 머리 삽입 때문에 컴퓨터구조가 먼저 큐에 들어가 2학기가 되었지만, 간선을 넣는 순서를 바꾸면 자료구조가 2학기가 될 수도 있습니다. 둘 다 “선행 조건을 어기지 않는” 정답입니다.

5.3 보너스: 사이클 감지기

이 알고리즘의 훌륭한 점은 덤으로 사이클을 감지한다는 것입니다.

    return count;                /* count < V 이면 사이클! */

정상적인 그래프라면 모든 정점이 언젠가 진입 차수 0이 되어 결과에 담깁니다. 그런데 사이클에 속한 정점들은 서로가 서로의 선행 조건이라 영원히 0이 되지 않습니다. 그래서 결과에 V개가 다 안 담기면 사이클이 있다는 증거입니다.

실행 결과에서 “졸업프로젝트 → C기초”라는 순환 조건을 넣자 정렬된 과목이 0개가 되었습니다. C기초의 진입 차수가 1이 되어 시작할 수 있는 과목이 하나도 없고, 여덟 과목 전부가 하나의 큰 순환 고리에 묶여 버린 것입니다.

이게 학문적인 이야기만은 아닙니다. 5주차의 make 로 실제로 만들어 봅시다. a 를 만들려면 b 가 먼저, b 를 만들려면 a 가 먼저 필요하다는 Makefile 입니다.

a: b
	touch a
b: a
	touch b

$ make
make: b <- a 상호 의존성은 무시됩니다.
touch b
touch a

영어 환경에서는 make: Circular b <- a dependency dropped. 입니다. make 는 의존 관계 그래프에서 사이클을 발견하면 간선 하나를 무시하고 진행합니다. 여러분이 큰 프로젝트에서 이 메시지를 만나면, 이제 그 뒤에서 어떤 알고리즘이 돌고 있는지 압니다. 패키지 매니저의 “순환 의존성” 오류, 스프레드시트의 “순환 참조” 경고도 전부 같은 원리입니다.

직접 해 보기: prereq[] 의 첫 두 줄 {0, 1} 과 {0, 4} 의 순서를 바꿔 보세요. 머리 삽입 때문에 C기초의 이웃 목록 순서가 바뀌어, 2학기가 컴퓨터구조에서 자료구조로 달라집니다. 8학기 졸업프로젝트는 그대로입니다. 어느 쪽이든 선행 조건을 어기지 않는지 확인해 보세요.

DFS로도 위상 정렬을 할 수 있습니다. DFS를 돌리며 “자식을 다 처리한 뒤” 정점을 스택에 쌓고, 끝나면 스택을 비우면 됩니다. Kahn 방식이 사이클 감지가 직관적이라 여기서는 이쪽을 골랐습니다. 연습 문제 4번에서 DFS 버전을 직접 만들어 보세요.

6. 최단 경로 1: 다익스트라

6.1 가중치가 있으면 BFS로는 안 된다

BFS가 최단 경로를 구해 준다고 했는데, 그건 모든 간선의 비용이 같을 때 이야기입니다. 간선마다 거리, 시간, 요금이 다르면 “간선 수가 적은 길”과 “비용이 적은 길”이 달라집니다.

집 --3-- 마트 --9-- 회사               간선 2개, 비용 12
집 --3-- 마트 --2-- 공원 --3-- 회사    간선 3개, 비용 8   <- 이쪽이 더 좋다!

BFS는 간선 수만 세므로 위쪽을 고릅니다. 틀린 답입니다. 가중치 그래프의 최단 경로에는 다익스트라(Dijkstra) 알고리즘이 필요합니다. 1959년에 네덜란드의 다익스트라가 카페에서 20분 만에 떠올렸다는 알고리즘인데, 지금도 모든 내비게이션의 뼈대입니다.

아이디어는 탐욕법입니다.

아직 확정하지 않은 정점 중 현재 거리가 가장 짧은 정점은, 그 거리로 확정해도 된다.

왜 그럴까요? 그 정점에 더 짧은 우회로가 있으려면 다른 미확정 정점을 거쳐야 하는데, 그 정점까지의 거리가 이미 이 정점보다 크거나 같으니 우회로는 더 길 수밖에 없습니다. 단, 이 논리는 간선 가중치가 음수가 아닐 때만 성립합니다. 이 전제가 깨지면 어떻게 되는지는 6.4절에서 실제로 봅니다.

examples/dijkstra.c:

/*
 * dijkstra.c - 다익스트라 최단 경로
 * 14주차: 그래프 자료구조와 탐색
 *
 * BFS는 "간선 수" 기준 최단이었습니다. 간선마다 가중치(거리, 시간,
 * 비용)가 다르면? 다익스트라가 답입니다.
 *
 * 아이디어 (탐욕법):
 * 1. 출발점의 거리 0, 나머지 무한대
 * 2. 미확정 정점 중 거리가 가장 짧은 것을 "확정"한다
 *    (더 짧은 우회로가 있을 수 없다 - 음수 간선이 없다면!)
 * 3. 확정 정점의 이웃 거리를 갱신(완화, relax)한다
 * 4. 모두 확정될 때까지 반복
 *
 * 이 예제는 이해가 쉬운 O(V^2) 배열 버전입니다.
 * (12주차의 최소 힙을 쓰면 O(E log V) - 프로젝트에서!)
 */
#include <stdio.h>
#include <limits.h>

#define V 6
#define INF INT_MAX

static const char *name[V] = {"집", "카페", "학교", "공원", "마트", "회사"};

/* 인접 행렬 (0 = 간선 없음, 무방향) */
static int graph[V][V] = {
    /*        집 카페 학교 공원 마트 회사 */
    /* 집  */ { 0,  4,   0,   7,  3,   0 },
    /* 카페*/ { 4,  0,   2,   0,  0,   0 },
    /* 학교*/ { 0,  2,   0,   1,  0,   5 },
    /* 공원*/ { 7,  0,   1,   0,  2,   3 },
    /* 마트*/ { 3,  0,   0,   2,  0,   9 },
    /* 회사*/ { 0,  0,   5,   3,  9,   0 },
};

void dijkstra(int start, int dist[], int parent[]) {
    int done[V] = {0};           /* 확정 여부 */

    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[start] = 0;

    for (int round = 0; round < V; round++) {
        /* 1. 미확정 중 최소 거리 정점 찾기 (배열 버전의 O(V) 부분) */
        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!done[i] && dist[i] != INF && (u < 0 || dist[i] < dist[u])) {
                u = i;
            }
        }
        if (u < 0) break;        /* 남은 정점은 도달 불가 */
        done[u] = 1;             /* 확정! 이보다 짧은 길은 없다 */

        printf("  확정: %-4s (거리 %d)\n", name[u], dist[u]);

        /* 2. u를 경유하는 길이 더 짧으면 갱신 (완화) */
        for (int v = 0; v < V; v++) {
            if (graph[u][v] == 0 || done[v]) continue;
            if (dist[u] + graph[u][v] < dist[v]) {
                if (dist[v] != INF) {
                    printf("      %s: %d -> %d (%s 경유가 더 짧다!)\n",
                           name[v], dist[v], dist[u] + graph[u][v], name[u]);
                }
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
            }
        }
    }
}

void print_path(const int parent[], int v) {
    if (parent[v] == -1) {
        printf("%s", name[v]);
        return;
    }
    print_path(parent, parent[v]);
    printf(" -> %s", name[v]);
}

int main(void) {
    printf("동네 지도 (간선 = 이동 시간, 분):\n");
    printf("  집-카페 4, 집-공원 7, 집-마트 3, 카페-학교 2,\n");
    printf("  학교-공원 1, 학교-회사 5, 공원-마트 2, 공원-회사 3, 마트-회사 9\n");

    int dist[V], parent[V];

    printf("\n=== 다익스트라 실행 (집에서 출발) ===\n");
    dijkstra(0, dist, parent);

    printf("\n=== 결과: 집에서 각 장소까지 ===\n");
    printf("%-6s %-6s %s\n", "장소", "시간", "최단 경로");
    printf("--------------------------------------\n");
    for (int i = 0; i < V; i++) {
        printf("%-6s %4d분  ", name[i], dist[i]);
        print_path(parent, i);
        printf("\n");
    }

    printf("\n관찰:\n");
    printf("1. 회사까지 직행 느낌인 '마트(3)->회사(9)' = 12분이 아니라\n");
    printf("   마트->공원->회사 = 3+2+3 = 8분이 최단!\n");
    printf("2. 확정 순서는 거리 오름차순 (가까운 곳부터 확정)\n");
    printf("3. 음수 간선이 있으면? '확정'이 성립하지 않는다\n");
    printf("   -> 그때는 다음 예제의 벨만-포드!\n");

    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/dijkstra.c -o build/dijkstra
$ ./build/dijkstra
동네 지도 (간선 = 이동 시간, 분):
  집-카페 4, 집-공원 7, 집-마트 3, 카페-학교 2,
  학교-공원 1, 학교-회사 5, 공원-마트 2, 공원-회사 3, 마트-회사 9

=== 다익스트라 실행 (집에서 출발) ===
  확정: 집  (거리 0)
  확정: 마트 (거리 3)
      공원: 7 -> 5 (마트 경유가 더 짧다!)
  확정: 카페 (거리 4)
  확정: 공원 (거리 5)
      회사: 12 -> 8 (공원 경유가 더 짧다!)
  확정: 학교 (거리 6)
  확정: 회사 (거리 8)

=== 결과: 집에서 각 장소까지 ===
장소 시간 최단 경로
--------------------------------------
집       0분  집
카페    4분  집 -> 카페
학교    6분  집 -> 카페 -> 학교
공원    5분  집 -> 마트 -> 공원
마트    3분  집 -> 마트
회사    8분  집 -> 마트 -> 공원 -> 회사

관찰:
1. 회사까지 직행 느낌인 '마트(3)->회사(9)' = 12분이 아니라
   마트->공원->회사 = 3+2+3 = 8분이 최단!
2. 확정 순서는 거리 오름차순 (가까운 곳부터 확정)
3. 음수 간선이 있으면? '확정'이 성립하지 않는다
   -> 그때는 다음 예제의 벨만-포드!

다익스트라

6.2 거리표를 한 라운드씩 따라가기

프로그램 출력만으로는 여섯 정점의 거리가 동시에 어떻게 변하는지 보이지 않습니다. 라운드마다 dist[] 전체를 찍어 봤습니다. * 가 붙은 값은 확정된 것입니다.

단계	집	카페	학교	공원	마트	회사	이번 라운드에 일어난 일
시작	0	INF	INF	INF	INF	INF	출발점만 0
1) 집 확정	0*	4	INF	7	3	INF	집의 이웃 카페·공원·마트에 첫 거리
2) 마트 확정	0*	4	INF	5	3*	12	미확정 중 최소는 마트(3). 공원 7 → 5, 회사 12
3) 카페 확정	0*	4*	6	5	3*	12	최소는 카페(4). 학교 6
4) 공원 확정	0*	4*	6	5*	3*	8	최소는 공원(5). 회사 12 → 8
5) 학교 확정	0*	4*	6*	5*	3*	8	학교 경유 회사는 6 + 5 = 11 > 8, 갱신 없음
6) 회사 확정	0*	4*	6*	5*	3*	8*	끝

표를 세로로 읽으면 두 가지가 보입니다.

확정 순서는 거리 오름차순입니다. 0, 3, 4, 5, 6, 8. 매 라운드 “미확정 중 최소”를 고르니 당연하지만, 이 성질이 곧 알고리즘의 정당성입니다. 마트를 3으로 확정하는 순간, 다른 어떤 미확정 정점도 3 이상이므로 마트로 가는 더 짧은 우회로는 존재할 수 없습니다.

값은 줄어들기만 합니다. 공원은 7 → 5, 회사는 12 → 8 로 줄었고, 늘어난 적은 없습니다. 이 “줄이기”를 완화(relaxation) 라고 부릅니다.

        for (int v = 0; v < V; v++) {
            if (graph[u][v] == 0 || done[v]) continue;
            if (dist[u] + graph[u][v] < dist[v]) {
                ...
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
            }
        }

“지금까지 알던 v까지의 거리보다, u를 거쳐 가는 게 더 짧은가?”를 묻고, 짧으면 갱신하면서 parent[v] = u 로 “u에서 왔다”를 기록합니다. 4절 BFS의 parent 와 같은 역할이고, print_path 도 같은 함수입니다.

이 완화라는 개념은 다익스트라, 벨만-포드, 플로이드-워셜 세 알고리즘 모두의 공통 심장입니다. 셋의 차이는 “어떤 순서로, 몇 번 완화하느냐”뿐입니다.

• 다익스트라: 가까운 정점부터 한 번씩 (확정 순서가 중요)
• 벨만-포드: 모든 간선을 V − 1번 반복 (순서 무관, 우직하게)
• 플로이드-워셜: 모든 경유지에 대해 모든 쌍을 (완전 탐색)

이 구조를 알고 나면 세 알고리즘이 따로 노는 지식이 아니라 하나의 아이디어의 변주로 보입니다.

6.3 확정 정점 고르기와 O(V²)

        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!done[i] && dist[i] != INF && (u < 0 || dist[i] < dist[u])) {
                u = i;
            }
        }
        if (u < 0) break;        /* 남은 정점은 도달 불가 */
        done[u] = 1;             /* 확정! 이보다 짧은 길은 없다 */

조건이 세 개 겹쳐 있으니 하나씩 봅시다. !done[i] 는 아직 확정 안 된 것 중에서, dist[i] != INF 는 한 번이라도 도달한 것 중에서, u < 0 || dist[i] < dist[u] 는 첫 후보이거나 지금까지의 최소보다 작으면 갱신입니다. 4주차에서 배운 “배열에서 최솟값 찾기”에 조건 두 개를 덧붙인 것입니다.

“미확정 중 최소 거리”를 찾기 위해 매번 전체를 훑습니다. 이 부분이 O(V) 이고, V번 반복하므로 전체가 O(V²) 입니다. 정점 6개면 아무 문제가 없지만, 정점 100만 개짜리 도로망이면 1조 번입니다.

그런데 “최소 원소를 빠르게 꺼내기”라면 우리에게 더 좋은 도구가 있습니다. 12주차의 최소 힙입니다. 힙을 쓰면 O(E log V) 로 줄어듭니다. 프로젝트 1(GPS 내비게이션)에서 이 업그레이드를 직접 합니다.

직접 해 보기: graph[4][5](마트-회사)의 9를 2로 바꿔 보세요. 회사까지 집 → 마트 → 회사 = 5분이 되면서 확정 순서와 경로가 어떻게 달라지는지 출력으로 확인하세요. 그다음 집에서 아무 데도 갈 수 없도록 graph[0] 행을 전부 0으로 만들면, 집만 확정되고 u < 0 에서 멈추는 것도 볼 수 있습니다.

if (u < 0) break; 도 중요합니다. 미확정 정점이 전부 INF 라면 그것들은 출발점에서 닿을 수 없는 정점입니다. 그래프가 여러 섬으로 나뉘어 있을 때 그 정점들을 억지로 확정하지 않고 멈추는 안전장치입니다.

6.4 실험: 음수 간선을 넣으면 정말 틀리나

“음수 간선이 있으면 확정이 성립하지 않는다”를 확인해 봅시다. 정점 네 개짜리 방향 그래프입니다.

A --2--> B --1--> D
A --5--> C --(-4)--> B        A에서 B까지: 직행 2, 또는 A->C->B = 5 + (-4) = 1

진짜 최단은 C를 거치는 1입니다. 같은 다익스트라 코드에 이 그래프를 넣고, 7절에서 배울 벨만-포드의 답과 비교했습니다.

$ ./dijk_neg
  확정: A = 0
  확정: B = 2
  확정: D = 3
  확정: C = 5
다익스트라 답: A->B = 2, A->D = 3
벨만-포드 답: A->B = 1, A->D = 2   (A->C->B = 5 + (-4) = 1)

다익스트라가 틀렸습니다. B를 2로 확정한 뒤에야 C(5)가 확정되는데, C에서 B로 가는 −4 간선이 있다는 것을 그때 알아도 B는 이미 확정되어 되돌릴 수 없습니다. “더 먼 정점을 거치면 더 길어진다”는 전제가 음수 간선 앞에서 무너진 것입니다. 이 오답은 오류 메시지 없이 조용히 나옵니다. 가중치에 음수가 섞일 가능성이 있다면 다익스트라를 쓰면 안 됩니다.

6.5 INF 와 오버플로

이 예제는 INF 로 INT_MAX(2,147,483,647)를 씁니다.

#define INF INT_MAX

8절 플로이드-워셜은 INF 를 99999 로 두는데, 왜 다를까요? 여기서는 INF + 가중치 를 절대 계산하지 않기 때문입니다.

완화는 dist[u] + graph[u][v] 형태인데, u 는 방금 확정된 정점이라 dist[u] 가 항상 유한합니다(확정 후보를 고를 때 dist[i] != INF 조건을 걸었습니다). 그래서 오버플로가 날 일이 없습니다.

반면 플로이드-워셜은 dist[i][k] + dist[k][j] 를 무조건 계산하므로 INF + INF 가 발생합니다. 2주차에서 배운 대로 INT_MAX + 1 은 정의되지 않은 동작이고, 실제로는 음수로 감싸 돌아 비교가 전부 꼬입니다. 8.4절에서 실제로 꼬이는 모습을 봅니다.

같은 INF 라는 이름을 쓰더라도 그 값으로 덧셈을 하느냐에 따라 선택이 달라진다는 것, 초보자가 놓치기 쉬운 함정이니 기억해 두세요.

7. 최단 경로 2: 벨만-포드

7.1 음수 간선이라는 복병

6.4절에서 다익스트라가 음수 간선 앞에서 틀리는 것을 봤습니다. 음수 간선이 현실에 있냐고요? 있습니다.

• 환급, 보조금, 쿠폰이 붙은 경로 비용
• 화학 반응의 발열과 흡열 에너지
• 환율 변환 그래프(로그를 씌우면 음수가 생깁니다)
• 게임에서 “지나가면 체력을 주는 칸”

벨만-포드(Bellman-Ford) 의 접근은 우직합니다. 확정 같은 건 하지 않고, 모든 간선을 V − 1번 반복해서 완화합니다.

왜 V − 1번일까요? 최단 경로는 같은 정점을 두 번 지나지 않으므로(지나면 그 사이 구간을 빼는 게 더 짧으니까요) 간선을 최대 V − 1개 씁니다. 한 라운드가 끝날 때마다 “간선 k개짜리 최단 경로”까지는 확실히 맞아지므로, V − 1 라운드면 반드시 수렴합니다.

examples/bellman_ford.c:

/*
 * bellman_ford.c - 벨만-포드: 음수 간선도 되는 최단 경로
 * 14주차: 그래프 자료구조와 탐색
 *
 * 다익스트라의 한계: 음수 간선이 있으면 "확정"이 틀릴 수 있다.
 * (환급, 보조금, 환율 차익... 음수 비용은 현실에 존재합니다)
 *
 * 벨만-포드의 아이디어는 우직합니다:
 *   "모든 간선을 V-1번 반복해서 완화한다"
 * 최단 경로는 간선을 최대 V-1개 쓰므로, V-1번이면 반드시 수렴합니다.
 *
 * 보너스: V번째에도 갱신되면? 음수 사이클(돌수록 이득!)이 있다는
 * 증거입니다. "최단 경로"라는 개념 자체가 무너지는 상황을 감지!
 */
#include <stdio.h>
#include <limits.h>

#define V 5
#define INF INT_MAX

static const char *name[V] = {"A", "B", "C", "D", "E"};

typedef struct {
    int from, to, weight;
} Edge;

/* 방향 간선 목록 (간선 리스트 표현 - 벨만-포드에 딱 맞다) */
static Edge edges[] = {
    {0, 1,  6},      /* A -> B  6 */
    {0, 2,  7},      /* A -> C  7 */
    {1, 2,  8},      /* B -> C  8 */
    {1, 3, -4},      /* B -> D -4  (음수 간선!) */
    {1, 4,  5},      /* B -> E  5 */
    {2, 3,  9},      /* C -> D  9 */
    {2, 4, -3},      /* C -> E -3  (음수 간선!) */
    {3, 0,  2},      /* D -> A  2 */
    {4, 3,  7},      /* E -> D  7 */
};
#define E ((int)(sizeof(edges) / sizeof(edges[0])))

/* 벨만-포드. 음수 사이클이 있으면 0, 정상이면 1 반환 */
int bellman_ford(int start, int dist[], int parent[]) {
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[start] = 0;

    /* V-1 라운드: 모든 간선을 완화 */
    for (int round = 1; round <= V - 1; round++) {
        int changed = 0;
        for (int e = 0; e < E; e++) {
            int u = edges[e].from, v = edges[e].to, w = edges[e].weight;
            if (dist[u] == INF) continue;        /* 아직 못 간 곳 경유 불가 */
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                changed = 1;
            }
        }
        printf("  라운드 %d: ", round);
        for (int i = 0; i < V; i++) {
            if (dist[i] == INF) printf("%s=INF ", name[i]);
            else                printf("%s=%d ", name[i], dist[i]);
        }
        printf("%s\n", changed ? "" : "(변화 없음 - 조기 수렴!)");
        if (!changed) break;
    }

    /* V번째 검사: 여기서도 줄어들면 음수 사이클 */
    for (int e = 0; e < E; e++) {
        int u = edges[e].from, v = edges[e].to, w = edges[e].weight;
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return 0;            /* 음수 사이클! */
        }
    }
    return 1;
}

void print_path(const int parent[], int v) {
    if (parent[v] == -1) { printf("%s", name[v]); return; }
    print_path(parent, parent[v]);
    printf(" -> %s", name[v]);
}

int main(void) {
    printf("방향 그래프 (음수 간선 포함):\n");
    for (int e = 0; e < E; e++) {
        printf("  %s -> %s : %d\n",
               name[edges[e].from], name[edges[e].to], edges[e].weight);
    }

    int dist[V], parent[V];

    printf("\n=== 벨만-포드 실행 (A에서 출발) ===\n");
    int ok = bellman_ford(0, dist, parent);

    if (ok) {
        printf("\n=== 결과 ===\n");
        for (int i = 0; i < V; i++) {
            printf("A -> %s: 거리 %2d, 경로 ", name[i], dist[i]);
            print_path(parent, i);
            printf("\n");
        }
        printf("\nB->D가 -4라서 A->B->D = 6-4 = 2가 최단!\n");
        printf("(다익스트라였다면 D를 너무 일찍 확정해 틀릴 수 있는 상황)\n");
    } else {
        printf("\n음수 사이클 발견! 최단 경로가 정의되지 않습니다.\n");
    }

    printf("\n=== 음수 사이클 실험 ===\n");
    printf("D->A 가중치를 2에서 -3으로 바꾸면\n");
    printf("B->D->A->B = -4 + (-3) + 6 = -1 (돌수록 이득인 사이클!)\n");
    edges[7].weight = -3;
    ok = bellman_ford(0, dist, parent);
    printf("\n판정: %s\n",
           ok ? "정상" : "음수 사이클 감지! (환차익 거래 탐지의 원리)");

    printf("\n다익스트라 vs 벨만-포드:\n");
    printf("  다익스트라 O(V^2 or E log V): 빠름, 음수 불가\n");
    printf("  벨만-포드  O(V x E)         : 느림, 음수 OK + 사이클 감지\n");
    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/bellman_ford.c -o build/bellman_ford
$ ./build/bellman_ford
방향 그래프 (음수 간선 포함):
  A -> B : 6
  A -> C : 7
  B -> C : 8
  B -> D : -4
  B -> E : 5
  C -> D : 9
  C -> E : -3
  D -> A : 2
  E -> D : 7

=== 벨만-포드 실행 (A에서 출발) ===
  라운드 1: A=0 B=6 C=7 D=2 E=4
  라운드 2: A=0 B=6 C=7 D=2 E=4 (변화 없음 - 조기 수렴!)

=== 결과 ===
A -> A: 거리  0, 경로 A
A -> B: 거리  6, 경로 A -> B
A -> C: 거리  7, 경로 A -> C
A -> D: 거리  2, 경로 A -> B -> D
A -> E: 거리  4, 경로 A -> C -> E

B->D가 -4라서 A->B->D = 6-4 = 2가 최단!
(다익스트라였다면 D를 너무 일찍 확정해 틀릴 수 있는 상황)

=== 음수 사이클 실험 ===
D->A 가중치를 2에서 -3으로 바꾸면
B->D->A->B = -4 + (-3) + 6 = -1 (돌수록 이득인 사이클!)
  라운드 1: A=-1 B=6 C=7 D=2 E=4
  라운드 2: A=-2 B=5 C=6 D=1 E=3
  라운드 3: A=-3 B=4 C=5 D=0 E=2
  라운드 4: A=-4 B=3 C=4 D=-1 E=1

판정: 음수 사이클 감지! (환차익 거래 탐지의 원리)

다익스트라 vs 벨만-포드:
  다익스트라 O(V^2 or E log V): 빠름, 음수 불가
  벨만-포드  O(V x E)         : 느림, 음수 OK + 사이클 감지

7.2 간선 목록이라는 표현

이 예제는 그래프를 인접 리스트도 행렬도 아닌 간선 목록으로 저장합니다.

typedef struct {
    int from, to, weight;
} Edge;

static Edge edges[] = {
    {0, 1,  6},      /* A -> B  6 */
    {1, 3, -4},      /* B -> D -4  (음수 간선!) */
    ...
};
#define E ((int)(sizeof(edges) / sizeof(edges[0])))

8주차 구조체의 배열입니다. E 를 매크로로 정의한 줄은 4주차에서 배운 “배열 길이 = 전체 크기 ÷ 원소 크기”입니다. 간선을 하나 추가해도 E 가 알아서 바뀝니다.

벨만-포드는 “모든 간선을 순회”하는 것이 알고리즘의 전부라, 간선이 배열에 나란히 있는 이 표현이 가장 편합니다. 알고리즘마다 어울리는 표현이 다르다는 말을 2절에서 했는데, 그 구체적인 예입니다. 10절의 크루스칼도 같은 이유로 간선 목록을 씁니다.

7.3 핵심 루프

    for (int round = 1; round <= V - 1; round++) {
        int changed = 0;
        for (int e = 0; e < E; e++) {
            int u = edges[e].from, v = edges[e].to, w = edges[e].weight;
            if (dist[u] == INF) continue;        /* 아직 못 간 곳 경유 불가 */
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                changed = 1;
            }
        }
        ...
        if (!changed) break;
    }

완화 조건 dist[u] + w < dist[v] 는 다익스트라와 완전히 같습니다. 차이는 순서를 따지지 않고 모든 간선을 반복한다는 것뿐입니다.

라운드 1이 어떻게 A=0 B=6 C=7 D=2 E=4 를 만드는지, 간선 목록 순서대로 아홉 번의 완화를 따라가 봅시다. 시작은 A = 0, 나머지는 INF 입니다.

간선	계산 dist[u] + w	비교 대상 dist[v]	결과
A→B (6)	0 + 6 = 6	INF	B = 6
A→C (7)	0 + 7 = 7	INF	C = 7
B→C (8)	6 + 8 = 14	7	더 기니 그대로
B→D (−4)	6 + (−4) = 2	INF	D = 2
B→E (5)	6 + 5 = 11	INF	E = 11
C→D (9)	7 + 9 = 16	2	그대로
C→E (−3)	7 + (−3) = 4	11	E = 4
D→A (2)	2 + 2 = 4	0	그대로
E→D (7)	4 + 7 = 11	2	그대로

한 라운드 안에서도 앞 간선이 만든 값을 뒤 간선이 곧바로 씁니다. B→D 는 그 직전에 정해진 B = 6 을 썼고, C→E 는 B→E 가 만든 11 을 4 로 끌어내렸습니다. 이 그래프는 간선 목록이 마침 “출발점에서 먼 순서”로 잘 배열되어 있어 한 라운드에 끝났습니다. 다음 실험에서 그 운을 없애 봅니다.

두 가지 실무 기법이 들어 있습니다.

if (dist[u] == INF) continue; 아직 도달하지 못한 정점을 경유지로 삼을 수는 없습니다. 동시에 이 검사가 INF + w 오버플로도 막아 줍니다. 6.5절에서 이야기한 함정을 여기서는 이렇게 처리합니다.

if (!changed) break; 한 라운드에 아무 변화도 없었다면 더 돌아도 변화가 없습니다. 조기 종료입니다. 실행 결과에서 라운드 2가 “(변화 없음 – 조기 수렴!)”으로 끝난 게 이것입니다. 이론상 V − 1 = 4라운드지만 실제로는 2라운드에 끝났습니다.

7.4 실험: 간선 순서를 바꾸면 라운드 수가 달라진다

첫 실행이 1라운드 만에 정답에 도달한 것은 운이 좋아서입니다. 간선 목록의 순서가 결과에는 영향을 주지 않지만 라운드 수에는 영향을 줍니다. 정점 5개를 한 줄로 이은 그래프(0→1→2→3→4, 각 1)로 확인했습니다.

$ ./bf_order
앞에서 뒤 순서 라운드 2 에 수렴  (거리: 0 1 2 3 4 )
뒤에서 앞 순서 라운드 4 에 수렴  (거리: 0 1 2 3 4 )

간선을 0→1, 1→2, 2→3, 3→4 순서로 두면 1라운드 안에 물결이 끝까지 전파되어 2라운드째 “변화 없음”으로 끝납니다. 거꾸로 3→4, 2→3, 1→2, 0→1 순서면 라운드마다 한 칸씩만 전파되어 꼬박 4라운드가 걸립니다. 최악의 경우가 정확히 V − 1 라운드이고, 그것이 “V − 1번이면 충분하다”는 보장의 의미입니다. 거리는 어느 쪽이든 같습니다.

7.5 진짜 보석: 음수 사이클 감지

벨만-포드의 진짜 가치는 여기 있습니다.

    /* V번째 검사: 여기서도 줄어들면 음수 사이클 */
    for (int e = 0; e < E; e++) {
        int u = edges[e].from, v = edges[e].to, w = edges[e].weight;
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return 0;            /* 음수 사이클! */
        }
    }

V − 1 라운드면 수렴이 보장된다고 했습니다. 그런데 V번째에도 거리가 줄어든다면? 돌수록 이득인 사이클이 있다는 뜻입니다.

실행 결과의 실험을 보세요. D->A 를 2에서 −3으로 바꾸면 B->D->A->B = -4 + (-3) + 6 = -1 이 됩니다. 이 고리를 한 바퀴 돌 때마다 비용이 1씩 줄어듭니다. 라운드마다 A가 −1, −2, −3, −4로 계속 내려가는 출력이 그 증거입니다. 무한히 돌면 거리가 음의 무한대로 갑니다.

이런 상황에서는 “최단 경로”라는 개념 자체가 정의되지 않습니다. 답이 없다는 것을 알려 주는 것이 이 검사의 역할입니다.

그리고 이게 실무에서 진짜 쓰입니다. 환차익 거래(arbitrage) 탐지가 대표적입니다. 통화를 정점으로, 환율을 간선으로 놓고 가중치에 -log(환율) 을 쓰면, 음수 사이클이 곧 “환전을 한 바퀴 돌리면 돈이 불어나는 경로”가 됩니다. 금융권에서 벨만-포드가 실제로 이 목적으로 돌아갑니다.

8. 최단 경로 3: 플로이드-워셜

8.1 모든 쌍을 한 방에

다익스트라와 벨만-포드는 “한 출발점”에서의 최단 경로였습니다. 그런데 모든 정점 쌍 사이의 거리표가 필요하다면요? 도시 간 거리표, 라우팅 테이블, 게임 맵의 이동 비용표 같은 것들입니다.

다익스트라를 V번 돌려도 되지만, 정점 수가 적다면 훨씬 간단한 방법이 있습니다. 플로이드-워셜(Floyd-Warshall) 은 삼중 루프 다섯 줄이 전부입니다.

for (int k = 0; k < V; k++)          /* 경유지 - 반드시 바깥! */
    for (int i = 0; i < V; i++)      /* 출발지 */
        for (int j = 0; j < V; j++)  /* 도착지 */
            if (dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];

의미는 이렇습니다. “i에서 j로 갈 때 k를 경유하면 더 짧은가?” 를 모든 경유지 k에 대해 시도합니다. 6.2절의 완화를 모든 쌍에 대해 하는 것입니다.

examples/floyd_warshall.c:

/*
 * floyd_warshall.c - 플로이드-워셜: 모든 쌍 최단 경로
 * 14주차: 그래프 자료구조와 탐색
 *
 * 다익스트라/벨만-포드는 "한 출발점"에서의 최단 경로였습니다.
 * "모든 정점 쌍" 사이의 최단 거리표가 필요하다면? 플로이드-워셜!
 *
 * 삼중 루프 다섯 줄이 전부입니다:
 *   for (k) for (i) for (j)
 *       if (dist[i][k] + dist[k][j] < dist[i][j]) 갱신
 *
 * 의미: "i에서 j로 갈 때, k를 경유하면 더 짧은가?"를
 * 모든 경유지 k에 대해 시도하는 것. 동적 계획법의 고전입니다.
 *
 * 주의: k(경유지)가 반드시 가장 바깥 루프여야 합니다!
 */
#include <stdio.h>

#define V 5
#define INF 99999        /* INT_MAX를 쓰면 덧셈 오버플로우! 큰 값으로 */

static const char *city[V] = {"서울", "대전", "대구", "부산", "광주"};

int main(void) {
    /* 도시 간 직행 거리 (0 = 자기 자신, INF = 직행 없음) */
    int dist[V][V] = {
        /*        서울  대전  대구  부산  광주 */
        /*서울*/ {   0,  140,  INF,  INF,  270 },
        /*대전*/ { 140,    0,  120,  INF,  170 },
        /*대구*/ { INF,  120,    0,   90,  INF },
        /*부산*/ { INF,  INF,   90,    0,  250 },
        /*광주*/ { 270,  170,  INF,  250,    0 },
    };
    printf("=== 직행 거리표 (INF = 직행 없음) ===\n      ");
    for (int j = 0; j < V; j++) printf("%6s", city[j]);
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("%6s", city[i]);
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) printf("%6s", "-");
            else                   printf("%6d", dist[i][j]);
        }
        printf("\n");
    }

    /* ---------- 플로이드-워셜 핵심 ---------- */
    for (int k = 0; k < V; k++) {            /* 경유지 (바깥!) */
        int updated = 0;
        for (int i = 0; i < V; i++) {        /* 출발지 */
            for (int j = 0; j < V; j++) {    /* 도착지 */
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    updated = 1;
                }
            }
        }
        if (updated) {
            printf("\n[%s 경유 허용] 갱신 발생!\n", city[k]);
        }
    }

    printf("\n=== 최종 최단 거리표 ===\n      ");
    for (int j = 0; j < V; j++) printf("%6s", city[j]);
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("%6s", city[i]);
        for (int j = 0; j < V; j++) printf("%6d", dist[i][j]);
        printf("\n");
    }

    printf("\n예시 해석:\n");
    printf("- 서울-부산 직행은 없지만 서울->대전->대구->부산 = %d\n",
           dist[0][3]);
    printf("- 서울-대구: 서울->대전->대구 = %d\n", dist[0][2]);

    printf("\n세 알고리즘 총정리:\n");
    printf("+------------+----------------+------------------+\n");
    printf("| 알고리즘   | 시간           | 용도             |\n");
    printf("+------------+----------------+------------------+\n");
    printf("| BFS        | O(V+E)         | 무가중치 한 출발 |\n");
    printf("| 다익스트라 | O(E log V)     | 가중치 한 출발   |\n");
    printf("| 벨만-포드  | O(VE)          | 음수 간선 OK     |\n");
    printf("| 플로이드   | O(V^3)         | 모든 쌍 (V 작을때)|\n");
    printf("+------------+----------------+------------------+\n");
    printf("\nINF에 INT_MAX를 안 쓴 이유: INF + 가중치가 오버플로우해서\n");
    printf("음수가 되면 비교가 전부 꼬입니다. 흔한 함정!\n");

    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/floyd_warshall.c -o build/floyd_warshall
$ ./build/floyd_warshall
=== 직행 거리표 (INF = 직행 없음) ===
      서울대전대구부산광주
서울     0   140     -     -   270
대전   140     0   120     -   170
대구     -   120     0    90     -
부산     -     -    90     0   250
광주   270   170     -   250     0

[대전 경유 허용] 갱신 발생!

[대구 경유 허용] 갱신 발생!

=== 최종 최단 거리표 ===
      서울대전대구부산광주
서울     0   140   260   350   270
대전   140     0   120   210   170
대구   260   120     0    90   290
부산   350   210    90     0   250
광주   270   170   290   250     0

예시 해석:
- 서울-부산 직행은 없지만 서울->대전->대구->부산 = 350
- 서울-대구: 서울->대전->대구 = 260
...

머리글의 도시 이름이 붙어 나오는 것도 %6s 가 바이트 폭이라 한글 두 글자(6바이트)에 남는 칸이 없기 때문입니다.

8.2 경유지를 하나씩 허용하며 표가 채워지는 과정

프로그램은 “갱신 발생!”만 알려 줍니다. k 단계마다 거리표 전체를 찍어 보면 동적 계획법이 무엇을 하는지 보입니다.

$ ./floyd_exp
[k=0: 서울 경유 허용] 갱신 0칸

[k=1: 대전 경유 허용] 갱신 4칸
      서울  대전  대구  부산  광주
서울     0   140   260     -   270
대전   140     0   120     -   170
대구   260   120     0    90   290
부산     -     -    90     0   250
광주   270   170   290   250     0

[k=2: 대구 경유 허용] 갱신 4칸
      서울  대전  대구  부산  광주
서울     0   140   260   350   270
대전   140     0   120   210   170
대구   260   120     0    90   290
부산   350   210    90     0   250
광주   270   170   290   250     0

[k=3: 부산 경유 허용] 갱신 0칸
[k=4: 광주 경유 허용] 갱신 0칸

• k = 1 (대전 경유 허용): 서울-대구가 140 + 120 = 260 으로, 대구-광주가 120 + 170 = 290 으로 채워집니다. 대칭이니 4칸입니다.
• k = 2 (대구 경유 허용): 이제 서울-부산이 채워집니다. 서울-대구 260 은 방금 전 단계에서 대전 경유로 얻은 값이고, 거기에 대구-부산 90 을 더해 350 입니다.

서울→대전→대구→부산이라는 세 단계 경유를 알고리즘이 따로 다루지 않았다는 점이 핵심입니다. k = 1 에서 얻은 결과(서울-대구 260)를 k = 2 에서 재료로 썼습니다. 경유지를 하나씩 늘려 가며 이전 결과를 재활용하는 것, 이것이 동적 계획법(dynamic programming)이고, 17주차에서 본격적으로 다룹니다.

정확히 말하면 k번째 바깥 루프가 끝난 시점의 dist[i][j] 는 “0번부터 k번까지만 경유지로 허용했을 때의 i→j 최단 거리” 입니다. 이 정의가 다음 실험의 열쇠입니다.

8.3 실험: 루프 순서를 바꾸면

이 알고리즘에서 가장 유명한 함정은 루프 순서입니다. k를 안쪽으로 옮겨 i, j, k 순서로 돌리면 어떻게 될까요? 먼저 이 예제의 5개 도시로 해 봤습니다.

$ ./floyd_exp w
[i-j-k 순서] 결과:
      서울  대전  대구  부산  광주
서울     0   140   260   350   270
...   (올바른 순서와 완전히 같음)

맞는 답이 나왔습니다. 그러면 순서는 상관없는 걸까요? 아닙니다. 이 그래프에서는 우연히 맞은 것입니다. 정점 번호 순서와 경로의 방향이 맞아떨어져서, 필요한 중간 결과가 마침 먼저 계산되었을 뿐입니다. 이런 우연이 이 버그를 더 위험하게 만듭니다. 테스트 몇 개는 통과하고, 실제 데이터에서 틀립니다.

틀리는 그래프를 만들어 봅시다. 0→3→2→1 로 이어진 방향 사슬입니다(각 간선 1). 0에서 1까지 정답은 3입니다.

$ ./floyd_wrong3
               0->3   0->2   0->1
k-i-j (정답)      1      2      3
i-j-k             1      2  99999   (99999 = INF, 못 간다는 뜻)

i, j, k 순서에서는 0→1 이 INF, 즉 “갈 수 없다” 로 나옵니다. 왜일까요? i = 0, j = 1 일 때 k = 3 을 시도하면 dist[0][3] + dist[3][1] 인데, dist[3][1] (3→2→1 = 2)은 i = 3 인 행을 처리할 때 계산되므로 아직 INF 입니다. 행 0의 처리가 끝난 뒤에 행 3이 채워져도 행 0으로 돌아가지 않습니다. 8.2절의 정의(“k까지 허용했을 때의 최단 거리”)가 무너진 것입니다.

컴파일 오류도, 경고도, 실행 오류도 없습니다. 답만 조용히 틀립니다. 그래서 이 알고리즘을 쓸 때는 k가 바깥이라는 것을 주문처럼 외워야 합니다. 예제가 [대전 경유 허용] 처럼 단계를 출력하는 것도 “지금 k를 늘려 가는 중”이라는 의미를 눈으로 보라고 넣은 장치입니다.

8.4 실험: INF 에 INT_MAX 를 쓰면

#define INF 99999        /* INT_MAX를 쓰면 덧셈 오버플로우! 큰 값으로 */

6.5절에서 예고한 함정입니다. 직접 밟아 봅시다. 정점 세 개(0-1 연결, 2는 외톨이)에 INF = INT_MAX 를 쓴 플로이드-워셜입니다.

$ ./floyd_intmax
           0           5 -2147483641
           5           0 -2147483646
 -2147483641 -2147483646          -4

거리표가 엉망입니다. 외톨이인 2번까지의 거리가 −21억이고, 2에서 2로 가는 거리가 −4입니다. dist[0][2] + dist[2][1] 이 INT_MAX + INT_MAX 가 되어 음수로 감겨 돌아가고, 그 음수가 “INF 보다 짧은 경로”로 채택된 것입니다. 2주차에서 배운 부호 있는 정수 오버플로가 정확히 이렇게 나타납니다.

컴파일러의 검사기를 켜면 어디서 터지는지 알려 줍니다.

$ gcc -fsanitize=undefined floyd_intmax.c -o floyd_intmax_ub && ./floyd_intmax_ub
floyd_intmax.c:7:101: runtime error: signed integer overflow: 5 + 2147483647 cannot be represented in type 'int'

해법은 두 가지입니다.

1. 충분히 큰 유한값 쓰기 (예제가 쓴 방법): 실제 거리의 최댓값보다는 크고, 둘을 더해도 넘치지 않는 값. 99999 정도면 됩니다.
2. 덧셈 전에 검사하기: if (dist[i][k] != INF && dist[k][j] != INF) 를 앞에 붙입니다.

1번이 코드가 단순해서 널리 쓰이지만, 실제 가중치가 커질 수 있는 상황이라면 2번이 안전합니다. 어느 쪽이든 INF 로 덧셈을 하는 알고리즘인가를 먼저 확인하는 습관이 중요합니다.

8.5 세 알고리즘 총정리

알고리즘	시간	음수 간선	용도	함정
BFS	O(V + E)	—	무가중치, 한 출발점	표시는 넣을 때
다익스트라	O(V²) 또는 O(E log V)	불가 (6.4절)	가중치, 한 출발점	음수 간선
벨만-포드	O(VE)	가능 + 사이클 감지	음수가 있을 때	느림
플로이드-워셜	O(V³)	가능 (음수 사이클은 불가)	모든 쌍, V가 작을 때	k가 바깥, INF 오버플로

선택 기준을 순서대로 물어보면 됩니다.

1. 모든 쌍이 필요한가? → 정점이 적으면(수백 개 이하) 플로이드-워셜
2. 음수 간선이 있는가? → 벨만-포드
3. 가중치가 있는가? → 다익스트라
4. 다 아니면 → BFS (가장 빠릅니다)

9. Union-Find: “같은 그룹인가?”의 달인

9.1 연산 두 개짜리 자료구조

MST로 넘어가기 전에 도구 하나를 만들어야 합니다. Union-Find(서로소 집합, Disjoint Set)는 연산이 딱 두 개뿐인 단순한 자료구조입니다.

• find(x): x가 속한 그룹의 대표를 찾는다
• union(x, y): x의 그룹과 y의 그룹을 합친다

이걸로 뭘 할 수 있냐면, “두 원소가 같은 그룹인가?”를 find(x) == find(y) 로 즉시 판정할 수 있습니다. 3.6절에서 DFS로 연결 성분을 구할 때는 질문할 때마다 그래프 전체를 훑어야 했는데, Union-Find는 간선을 추가하면서 그룹 정보를 조금씩 갱신해 둡니다.

구현은 각 원소가 부모를 가리키는 숲(forest) 입니다. 12주차 트리를 거꾸로 쓴 것이라고 보면 됩니다. 자식이 부모를 가리키고, 대표는 자기 자신을 가리키는 뿌리입니다.

examples/union_find.c:

/*
 * union_find.c - Union-Find (서로소 집합, Disjoint Set)
 * 14주차: 그래프 자료구조와 탐색
 *
 * "두 원소가 같은 그룹인가?"를 빛의 속도로 답하는 자료구조입니다.
 * 연산 두 개뿐:
 *   find(x)     : x가 속한 그룹의 대표를 찾는다
 *   union(x, y) : x의 그룹과 y의 그룹을 합친다
 *
 * 구현: 각 원소가 "부모"를 가리키는 숲. 대표 = 뿌리.
 *
 * 두 가지 최적화로 사실상 O(1)이 됩니다:
 * 1. 경로 압축: find하는 길에 만난 노드를 전부 뿌리 직속으로
 * 2. 랭크 합치기: 작은 트리를 큰 트리 밑으로 (트리가 낮게 유지)
 *
 * 쓰임새: 크루스칼 MST(다음 예제), 네트워크 연결성, 이미지 영역 병합
 */
#include <stdio.h>

#define N 10

int parent[N];
int rank_[N];            /* rank는 일부 헤더와 충돌 위험이 있어 rank_ */

void uf_init(void) {
    for (int i = 0; i < N; i++) {
        parent[i] = i;           /* 처음엔 모두 자기 자신이 대표 */
        rank_[i] = 0;
    }
}

/* find + 경로 압축: 돌아오는 길에 전부 뿌리 직속으로 붙인다 */
int uf_find(int x) {
    if (parent[x] != x) {
        parent[x] = uf_find(parent[x]);      /* 재귀로 뿌리 찾고 직속 연결 */
    }
    return parent[x];
}

/* union + 랭크: 낮은 트리를 높은 트리 밑으로 */
int uf_union(int x, int y) {
    int rx = uf_find(x);
    int ry = uf_find(y);
    if (rx == ry) return 0;      /* 이미 같은 그룹 */

    if (rank_[rx] < rank_[ry]) {
        parent[rx] = ry;
    } else if (rank_[rx] > rank_[ry]) {
        parent[ry] = rx;
    } else {
        parent[ry] = rx;
        rank_[rx]++;             /* 높이가 같을 때만 랭크 증가 */
    }
    return 1;
}

int uf_same(int x, int y) {
    return uf_find(x) == uf_find(y);
}

void show_groups(void) {
    printf("  parent: ");
    for (int i = 0; i < N; i++) printf("%d ", parent[i]);
    printf("\n  그룹  : ");

    /* 대표별로 묶어 출력 */
    int printed[N] = {0};
    for (int i = 0; i < N; i++) {
        int root = uf_find(i);
        if (printed[root]) continue;
        printed[root] = 1;
        printf("{");
        for (int j = 0; j < N; j++) {
            if (uf_find(j) == root) printf("%d ", j);
        }
        printf("} ");
    }
    printf("\n");
}

int main(void) {
    uf_init();

    printf("=== 초기 상태: 10명이 각자 혼자 ===\n");
    show_groups();

    printf("\n=== 친구 맺기 (union) ===\n");
    struct { int a, b; } friends[] = {
        {0, 1}, {1, 2}, {3, 4}, {5, 6}, {6, 7}, {4, 5},
    };
    for (int i = 0; i < 6; i++) {
        printf("union(%d, %d)\n", friends[i].a, friends[i].b);
        uf_union(friends[i].a, friends[i].b);
    }
    show_groups();
    printf("  -> {0,1,2}, {3,4,5,6,7}, {8}, {9} 세력 형성!\n");

    printf("\n=== 같은 그룹인가? (find) ===\n");
    printf("0과 2: %s (0-1-2로 연결)\n", uf_same(0, 2) ? "같은 그룹" : "다른 그룹");
    printf("3과 7: %s (3-4-5-6-7로 연결)\n", uf_same(3, 7) ? "같은 그룹" : "다른 그룹");
    printf("0과 7: %s\n", uf_same(0, 7) ? "같은 그룹" : "다른 그룹");

    printf("\n=== 사이클 감지: union의 반환값 활용 ===\n");
    printf("이미 같은 그룹인 2와 0을 union하면?\n");
    int merged = uf_union(2, 0);
    printf("결과: %s\n", merged ? "새로 합쳐짐" : "이미 같은 그룹 (간선을 추가하면 사이클!)");
    printf("-> 크루스칼 MST가 사이클을 피하는 원리가 바로 이것!\n");

    printf("\n=== 경로 압축의 효과 ===\n");
    printf("find(7) 호출 후 parent 배열을 보면 7이 뿌리 직속이 되어 있다:\n");
    uf_find(7);
    show_groups();
    printf("  -> 다음 find(7)는 단 한 걸음!\n");

    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/union_find.c -o build/union_find
$ ./build/union_find
=== 초기 상태: 10명이 각자 혼자 ===
  parent: 0 1 2 3 4 5 6 7 8 9
  그룹  : {0 } {1 } {2 } {3 } {4 } {5 } {6 } {7 } {8 } {9 }

=== 친구 맺기 (union) ===
union(0, 1)
union(1, 2)
union(3, 4)
union(5, 6)
union(6, 7)
union(4, 5)
  parent: 0 0 0 3 3 3 5 5 8 9
  그룹  : {0 1 2 } {3 4 5 6 7 } {8 } {9 }
  -> {0,1,2}, {3,4,5,6,7}, {8}, {9} 세력 형성!

=== 같은 그룹인가? (find) ===
0과 2: 같은 그룹 (0-1-2로 연결)
3과 7: 같은 그룹 (3-4-5-6-7로 연결)
0과 7: 다른 그룹

=== 사이클 감지: union의 반환값 활용 ===
이미 같은 그룹인 2와 0을 union하면?
결과: 이미 같은 그룹 (간선을 추가하면 사이클!)
-> 크루스칼 MST가 사이클을 피하는 원리가 바로 이것!

=== 경로 압축의 효과 ===
find(7) 호출 후 parent 배열을 보면 7이 뿌리 직속이 되어 있다:
  parent: 0 0 0 3 3 3 3 3 8 9
  그룹  : {0 1 2 } {3 4 5 6 7 } {8 } {9 }
  -> 다음 find(7)는 단 한 걸음!

유니온 파인드

9.2 union 마다 숲이 어떻게 변하나

parent 배열은 “i번 원소의 부모는 parent[i]”라는 뜻입니다. 자기 자신을 가리키면 뿌리입니다. 여섯 번의 union 마다 배열이 어떻게 변하는지 찍어 봤습니다.

$ ./uf_trace
초기       parent: 0 1 2 3 4 5 6 7 8 9   rank: 0 0 0 0 0 0 0 0 0 0
union(0,1)   parent: 0 0 2 3 4 5 6 7 8 9   rank: 1 0 0 0 0 0 0 0 0 0
union(1,2)   parent: 0 0 0 3 4 5 6 7 8 9   rank: 1 0 0 0 0 0 0 0 0 0
union(3,4)   parent: 0 0 0 3 3 5 6 7 8 9   rank: 1 0 0 1 0 0 0 0 0 0
union(5,6)   parent: 0 0 0 3 3 5 5 7 8 9   rank: 1 0 0 1 0 1 0 0 0 0
union(6,7)   parent: 0 0 0 3 3 5 5 5 8 9   rank: 1 0 0 1 0 1 0 0 0 0
union(4,5)   parent: 0 0 0 3 3 3 5 5 8 9   rank: 1 0 0 2 0 1 0 0 0 0
find(7) 경로: 7 -> 5 -> 3
find(7) 후  parent: 0 0 0 3 3 3 5 3 8 9   rank: 1 0 0 2 0 1 0 0 0 0

그림으로 그리면 이렇습니다. 화살표는 “부모를 가리킨다”입니다.

union(0,1):   0 <- 1              (같은 높이 0 끼리 → 1을 0 밑에, 0의 rank 1)
union(1,2):   0 <- 1              find(1)=0, find(2)=2. rank 1 > 0 → 2를 0 밑에
              0 <- 2
union(6,7):   5 <- 6              find(6)=5, find(7)=7. 7을 5 밑에
              5 <- 7
union(4,5):   3 <- 4  3 <- 5 <- 6 (find(4)=3, find(5)=5, 둘 다 rank 1 → 5를 3 밑에,
                       5 <- 7      3의 rank 2)

마지막 union(4,5) 뒤의 그룹 {3,4,5,6,7} 을 보면 7의 부모는 5, 5의 부모는 3입니다. find(7) 은 7 -> 5 -> 3 두 걸음입니다. 그런데 find(7) 을 한 번 부르고 난 뒤의 마지막 줄에서 parent[7] 이 3으로 바뀌어 있습니다. 이것이 경로 압축입니다.

9.3 최적화 1: 경로 압축

int uf_find(int x) {
    if (parent[x] != x) {
        parent[x] = uf_find(parent[x]);      /* 재귀로 뿌리 찾고 직속 연결 */
    }
    return parent[x];
}

세 줄짜리 함수인데 여기에 경로 압축(path compression) 이 들어 있습니다.

단순하게 만든다면 while (parent[x] != x) x = parent[x]; return x; 로 뿌리까지 타고 올라가기만 하면 됩니다. 그런데 이 코드는 한 걸음 더 나갑니다. 재귀에서 돌아 나오는 길에 parent[x] 에 뿌리를 직접 대입합니다. 5주차 재귀의 “돌아오는 길에 일하기”가 여기서도 쓰였습니다. 결과적으로 경로에 있던 모든 노드가 뿌리의 직속 자식이 됩니다.

find(7) 을 따라가 봅시다. parent[7] = 5 이니 uf_find(5) 를 부르고, parent[5] = 3 이니 uf_find(3) 을 부르고, 3은 뿌리라 3을 돌려줍니다. 돌아 나오면서 parent[5] = 3 (원래 3이었으니 그대로), parent[7] = 3 으로 고쳐 씁니다. 다음부터 find(7) 은 단 한 걸음입니다. 찾을 때마다 구조가 평평해지는, 스스로를 최적화하는 자료구조인 셈입니다.

9.4 최적화 2: 랭크로 합치기

    if (rank_[rx] < rank_[ry]) {
        parent[rx] = ry;
    } else if (rank_[rx] > rank_[ry]) {
        parent[ry] = rx;
    } else {
        parent[ry] = rx;
        rank_[rx]++;             /* 높이가 같을 때만 랭크 증가 */
    }

rank_ 는 트리의 높이(정확히는 높이의 상한)입니다. 두 그룹을 합칠 때 낮은 트리를 높은 트리 밑에 붙입니다. 반대로 하면 전체 높이가 1 늘어나지만, 이렇게 하면 높이가 그대로 유지됩니다. 높이가 같을 때만 어쩔 수 없이 1 늘어나고, 그때 뿌리의 rank_ 를 올립니다. 추적 출력에서 rank 가 바뀌는 순간이 정확히 “같은 높이끼리 합칠 때”뿐인 것을 확인해 보세요.

변수 이름이 rank_ 인 이유도 짚고 갑시다. rank 는 일부 시스템 헤더에서 이미 쓰는 이름이라 충돌할 수 있어 밑줄을 붙였습니다. C에는 네임스페이스가 없어서 이런 이름 충돌이 실제로 일어납니다. index, link, time, y1 같은 이름도 같은 이유로 조심해야 합니다(y1 은 math.h 의 베셀 함수입니다).

9.5 실험: 최적화가 없으면 얼마나 느린가

“사실상 O(1)” 이라는 말이 얼마나 큰 차이인지 재 봤습니다. 원소 100만 개를 0-1, 1-2, 2-3, … 순서로 이어 붙이되, 한쪽은 아무 최적화 없이 “뒤 뿌리를 앞 뿌리 밑에” 붙이고, 다른 쪽은 경로 압축과 랭크를 씁니다. 그다음 find 를 1,000번 부릅니다.

$ ./uf_bench
최적화 없음 : 트리 깊이 999999, union 999999회 3 ms, find 1000회 1457.6 ms
압축+랭크    : 트리 깊이 1, union 999999회 3 ms, find 1000회 0.0 ms

최적화가 없으면 트리가 깊이 100만짜리 한 줄이 됩니다. 10주차의 연결 리스트를 뿌리까지 끝없이 따라가는 것과 같아서, find 1,000번에 1.5초가 걸립니다. 최적화를 켜면 깊이가 1이고 1,000번이 0.0ms 입니다. 원소 수가 100만이라도 find 한 번에 두 걸음을 넘지 않습니다.

두 최적화를 함께 쓰면 연산 하나가 사실상 O(1) 입니다. 정확히는 역아커만 함수 α(n) 인데, 우주의 원자 수보다 큰 n 에서도 5 이하인 함수라 상수로 봐도 무방합니다.

9.6 union 의 반환값이 사이클 감지기

이 예제에서 가장 중요한 통찰입니다.

int uf_union(int x, int y) {
    int rx = uf_find(x);
    int ry = uf_find(y);
    if (rx == ry) return 0;      /* 이미 같은 그룹 */
    ... 합치기 ...
    return 1;
}

uf_union 이 0을 반환했다는 것은 두 정점이 이미 연결되어 있었다는 뜻입니다. 이미 연결된 두 정점을 잇는 간선을 추가하면? 사이클이 생깁니다. 실행 결과의 “이미 같은 그룹인 2와 0을 union하면?” 실험이 그것입니다. 이 한 줄의 판정이 다음 절 크루스칼 알고리즘의 핵심 부품이 됩니다.

10. 최소 신장 트리(MST)

10.1 문제 설정

마을 6곳에 수도관을 놓으려 합니다. 모든 마을이 연결되기만 하면 되고, 총 공사비는 최소여야 합니다.

이 답이 최소 신장 트리(MST, Minimum Spanning Tree) 입니다.

• 신장 트리(spanning tree): 모든 정점을 포함하면서 사이클이 없는 부분 그래프. 간선은 정확히 V − 1개입니다.
• 최소 신장 트리: 그중 가중치 합이 최소인 것.

왜 간선이 V − 1개일까요? 정점 V개를 연결하려면 최소 V − 1개가 필요하고(그보다 적으면 끊깁니다), V개 이상이면 사이클이 생기기 때문입니다(사이클의 간선 하나를 빼도 여전히 연결되니 최소가 아닙니다). 1절에서 “트리의 간선은 V − 1개”라고 한 것과 같은 이야기입니다.

두 고전 알고리즘이 있고, 둘 다 탐욕법인데 둘 다 최적해를 냅니다.

• 크루스칼(Kruskal): 싼 간선부터 집는다. 사이클이 생기면 버린다 (Union-Find 사용)
• 프림(Prim): 한 정점에서 시작해 트리를 키운다. 트리와 바깥을 잇는 가장 싼 간선을 계속 추가

examples/mst.c:

/*
 * mst.c - 최소 신장 트리: 크루스칼 & 프림
 * 14주차: 그래프 자료구조와 탐색
 *
 * 문제: 모든 정점을 "가장 싼 비용"으로 연결하라.
 * (마을들에 수도관/전선/광케이블 깔기!)
 *
 * 신장 트리 = 모든 정점을 잇는 간선 V-1개 (사이클 없음)
 * 최소 신장 트리(MST) = 그중 가중치 합이 최소인 것
 *
 * 두 고전 알고리즘 (둘 다 탐욕법):
 * - 크루스칼: 싼 간선부터 집는다. 사이클이 생기면 버린다 (Union-Find!)
 * - 프림    : 한 정점에서 시작해 트리를 키운다. 트리와 바깥을 잇는
 *             가장 싼 간선을 계속 추가 (다익스트라와 닮은꼴)
 */
#include <stdio.h>
#include <stdlib.h>

#define V 6
#define INF 99999

static const char *town[V] = {"A동", "B동", "C동", "D동", "E동", "F동"};

typedef struct {
    int u, v, w;
} Edge;

/* 간선 리스트 (무방향) */
static Edge edges[] = {
    {0, 1, 4}, {0, 2, 3}, {1, 2, 2}, {1, 3, 5},
    {2, 3, 6}, {2, 4, 4}, {3, 4, 1}, {3, 5, 7}, {4, 5, 8},
};
#define E ((int)(sizeof(edges) / sizeof(edges[0])))

/* ---------- Union-Find (앞 예제의 축약판) ---------- */
static int parent[V];

void uf_init(void) { for (int i = 0; i < V; i++) parent[i] = i; }
int  uf_find(int x) {
    if (parent[x] != x) parent[x] = uf_find(parent[x]);
    return parent[x];
}
int uf_union(int x, int y) {
    int rx = uf_find(x), ry = uf_find(y);
    if (rx == ry) return 0;
    parent[ry] = rx;
    return 1;
}

/* qsort용 간선 비교 (가중치 오름차순) */
int edge_cmp(const void *a, const void *b) {
    int wa = ((const Edge *)a)->w, wb = ((const Edge *)b)->w;
    return (wa > wb) - (wa < wb);
}

/* ---------- 크루스칼 ---------- */
int kruskal(void) {
    Edge sorted[E];
    for (int i = 0; i < E; i++) sorted[i] = edges[i];
    qsort(sorted, E, sizeof(Edge), edge_cmp);    /* 1. 간선을 싼 순으로 */

    uf_init();
    int total = 0, picked = 0;

    for (int i = 0; i < E && picked < V - 1; i++) {
        Edge *e = &sorted[i];
        if (uf_union(e->u, e->v)) {              /* 2. 사이클 안 생기면 채택 */
            printf("  채택: %s-%s (%d)\n", town[e->u], town[e->v], e->w);
            total += e->w;
            picked++;
        } else {
            printf("  거부: %s-%s (%d) <- 사이클!\n",
                   town[e->u], town[e->v], e->w);
        }
    }
    return total;
}

/* ---------- 프림 (인접 행렬, O(V^2) 버전) ---------- */
int prim(int start) {
    /* 간선 리스트 -> 인접 행렬 변환 */
    int g[V][V];
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++) g[i][j] = INF;
    for (int i = 0; i < E; i++) {
        g[edges[i].u][edges[i].v] = edges[i].w;
        g[edges[i].v][edges[i].u] = edges[i].w;
    }

    int in_tree[V] = {0};
    int min_cost[V];             /* 트리에 붙는 최소 비용 */
    int from[V];                 /* 어느 트리 정점에서 붙는가 */

    for (int i = 0; i < V; i++) { min_cost[i] = INF; from[i] = -1; }
    min_cost[start] = 0;

    int total = 0;
    for (int round = 0; round < V; round++) {
        /* 트리 밖에서 가장 싸게 붙일 수 있는 정점 */
        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!in_tree[i] && (u < 0 || min_cost[i] < min_cost[u])) u = i;
        }
        if (min_cost[u] == INF) break;           /* 연결 안 된 정점 */

        in_tree[u] = 1;
        total += min_cost[u];
        if (from[u] >= 0) {
            printf("  추가: %s-%s (%d)\n", town[from[u]], town[u], min_cost[u]);
        }

        /* 새 트리 정점 u 덕분에 더 싸게 붙일 수 있는 이웃 갱신 */
        for (int v = 0; v < V; v++) {
            if (!in_tree[v] && g[u][v] < min_cost[v]) {
                min_cost[v] = g[u][v];
                from[v] = u;
            }
        }
    }
    return total;
}

int main(void) {
    printf("마을 %d곳을 수도관으로 연결하기 (간선 = 공사 비용):\n", V);
    for (int i = 0; i < E; i++) {
        printf("  %s-%s: %d억\n", town[edges[i].u], town[edges[i].v], edges[i].w);
    }

    printf("\n=== 크루스칼: 싼 간선부터, 사이클은 Union-Find로 거부 ===\n");
    int k = kruskal();
    printf("총 비용: %d억\n", k);

    printf("\n=== 프림: A동에서 시작해 트리를 키운다 ===\n");
    int p = prim(0);
    printf("총 비용: %d억\n", p);

    printf("\n두 알고리즘 결과가 같다: %s (MST 비용은 유일!)\n",
           k == p ? "확인" : "버그?!");
    printf("\n선택 기준:\n");
    printf("- 크루스칼: 간선이 적을 때(희소). 정렬 O(E log E)가 지배\n");
    printf("- 프림    : 간선이 많을 때(밀집). 힙 쓰면 O(E log V)\n");
    printf("\n주의: MST(연결 비용 최소)와 최단 경로(이동 거리 최소)는\n");
    printf("다른 문제! MST 경로가 두 점 사이 최단이라는 보장은 없다.\n");

    return 0;
}

컴파일하고 실행합니다.

$ gcc -Wall -Wextra -std=c11 -g examples/mst.c -o build/mst
$ ./build/mst
마을 6곳을 수도관으로 연결하기 (간선 = 공사 비용):
  A동-B동: 4억
  A동-C동: 3억
  B동-C동: 2억
  B동-D동: 5억
  C동-D동: 6억
  C동-E동: 4억
  D동-E동: 1억
  D동-F동: 7억
  E동-F동: 8억

=== 크루스칼: 싼 간선부터, 사이클은 Union-Find로 거부 ===
  채택: D동-E동 (1)
  채택: B동-C동 (2)
  채택: A동-C동 (3)
  거부: A동-B동 (4) <- 사이클!
  채택: C동-E동 (4)
  거부: B동-D동 (5) <- 사이클!
  거부: C동-D동 (6) <- 사이클!
  채택: D동-F동 (7)
총 비용: 17억

=== 프림: A동에서 시작해 트리를 키운다 ===
  추가: A동-C동 (3)
  추가: C동-B동 (2)
  추가: C동-E동 (4)
  추가: E동-D동 (1)
  추가: D동-F동 (7)
총 비용: 17억

두 알고리즘 결과가 같다: 확인 (MST 비용은 유일!)

선택 기준:
- 크루스칼: 간선이 적을 때(희소). 정렬 O(E log E)가 지배
- 프림    : 간선이 많을 때(밀집). 힙 쓰면 O(E log V)

주의: MST(연결 비용 최소)와 최단 경로(이동 거리 최소)는
다른 문제! MST 경로가 두 점 사이 최단이라는 보장은 없다.

간선을 고른 순서는 완전히 다른데 총 비용은 똑같이 17억입니다. 그리고 채택된 간선 다섯 개(D-E, B-C, A-C, C-E, D-F)도 같습니다. 정점 6개에 간선 V − 1 = 5개, 사이클 없이 전부 연결. 신장 트리의 정의 그대로입니다.

10.2 크루스칼: 정렬 + Union-Find

int kruskal(void) {
    Edge sorted[E];
    for (int i = 0; i < E; i++) sorted[i] = edges[i];
    qsort(sorted, E, sizeof(Edge), edge_cmp);    /* 1. 간선을 싼 순으로 */

    uf_init();
    int total = 0, picked = 0;

    for (int i = 0; i < E && picked < V - 1; i++) {
        Edge *e = &sorted[i];
        if (uf_union(e->u, e->v)) {              /* 2. 사이클 안 생기면 채택 */
            ...
            picked++;
        }
        ...
    }
    return total;
}

알고리즘이 두 단계뿐입니다. 정렬하고, 앞에서부터 집되 사이클이면 버린다. 실행 결과를 한 줄씩 읽어 봅시다.

순서	간선	Union-Find 판정	결과	그때까지의 그룹
1	D-E (1)	다른 그룹	채택	{D,E}
2	B-C (2)	다른 그룹	채택	{D,E} {B,C}
3	A-C (3)	다른 그룹	채택	{D,E} {A,B,C}
4	A-B (4)	같은 그룹	거부	A와 B는 이미 C를 통해 연결. 넣으면 삼각형 사이클
5	C-E (4)	다른 그룹	채택	{A,B,C,D,E}
6	B-D (5)	같은 그룹	거부
7	C-D (6)	같은 그룹	거부
8	D-F (7)	다른 그룹	채택	전부 연결. 5개 채웠으니 끝

사이클 판정을 Union-Find가 사실상 O(1)에 해 주기 때문에 가능한 단순함입니다. 판정 없이 “싼 것부터 5개”를 집었다면 A-B(4)가 들어가 삼각형이 생기고 F동이 끊긴 채 끝났을 겁니다.

qsort 는 7주차에서 배운 표준 라이브러리 정렬입니다. 비교 함수를 다시 보세요.

int edge_cmp(const void *a, const void *b) {
    int wa = ((const Edge *)a)->w, wb = ((const Edge *)b)->w;
    return (wa > wb) - (wa < wb);
}

return wa - wb; 로 쓰는 코드를 많이 보셨을 텐데, 그건 뺄셈이 오버플로할 수 있어서 위험합니다. 7주차에서 경고했던 것을 직접 확인해 봤습니다.

$ ./cmp_overflow
a = 2147483647, b = -1
a - b = -2147483648  (음수! 'a가 작다'고 판정)
(a > b) - (a < b) = 1

INT_MAX - (-1) 은 INT_MAX + 1 이라 음수로 감깁니다. a가 b보다 훨씬 큰데 “작다”고 답하니 정렬이 엉망이 됩니다. (wa > wb) - (wa < wb) 는 항상 −1, 0, 1만 만들어 내는 안전한 관용구입니다. 15주차 정렬 편에서 다시 다룹니다.

picked < V - 1 조건도 작은 최적화입니다. 간선 V − 1개를 다 모았으면 남은 간선은 볼 필요가 없으니 일찍 멈춥니다. 실행 결과에서 E-F(8)이 아예 등장하지 않은 이유입니다.

10.3 프림: 트리를 키우기

    for (int round = 0; round < V; round++) {
        /* 트리 밖에서 가장 싸게 붙일 수 있는 정점 */
        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!in_tree[i] && (u < 0 || min_cost[i] < min_cost[u])) u = i;
        }
        if (min_cost[u] == INF) break;           /* 연결 안 된 정점 */

        in_tree[u] = 1;
        total += min_cost[u];
        ...
        /* 새 트리 정점 u 덕분에 더 싸게 붙일 수 있는 이웃 갱신 */
        for (int v = 0; v < V; v++) {
            if (!in_tree[v] && g[u][v] < min_cost[v]) {
                min_cost[v] = g[u][v];
                from[v] = u;
            }
        }
    }

6절의 다익스트라 코드와 나란히 놓고 비교해 보세요. 구조가 거의 똑같습니다.

	다익스트라	프림
고르는 기준	dist[] 최소 (출발점까지 누적 거리)	min_cost[] 최소 (트리에 붙는 간선 하나의 비용)
갱신 식	dist[u] + w < dist[v]	w < min_cost[v]
확정 표시	done[]	in_tree[]
결과	최단 경로 트리	최소 신장 트리

차이는 갱신 식 하나입니다. 다익스트라는 “출발점부터의 누적 거리”를, 프림은 “트리에 붙는 간선 하나의 비용”을 봅니다. 이 작은 차이가 완전히 다른 문제를 풉니다. 실행 결과에서 프림이 A동에서 시작해 C(3) → B(2) → E(4) → D(1) → F(7) 순으로 트리를 키우는 것을 보세요. 매 순간 “지금 트리에 가장 싸게 붙일 수 있는 마을”을 고릅니다.

10.4 실험: 같은 비용의 간선이 있으면

“MST 비용은 유일”이지만 MST 자체는 여러 개일 수 있습니다. 정점 3개를 삼각형으로 잇고 세 간선의 비용을 전부 2로 둔 그래프에서, 간선 목록의 순서만 바꿔 크루스칼을 두 번 돌렸습니다.

$ ./mst_tie
간선 순서 A: 0-1(2) 1-2(2) => 총 4
간선 순서 B: 0-2(2) 1-2(2) => 총 4

고른 간선은 다르지만 총비용은 같습니다. qsort 는 같은 값의 순서를 보장하지 않으므로(15주차에서 “안정 정렬”이라는 이름으로 다시 만납니다), 같은 가중치가 많은 그래프에서는 실행 환경에 따라 다른 MST가 나올 수 있습니다. 틀린 게 아닙니다. 채점 프로그램을 만든다면 간선 목록이 아니라 총비용을 비교해야 하는 이유입니다.

직접 해 보기: edges[] 에서 D동-F동(7)을 지우면 F동으로 가는 길은 E동-F동(8)뿐입니다. 크루스칼과 프림 모두 총비용이 18억이 되는지 확인해 보세요. 그다음 F동으로 가는 간선을 둘 다 지우면? 프림의 if (min_cost[u] == INF) break; 가 어떻게 동작하는지, 크루스칼은 간선을 몇 개 채택하고 끝나는지 보세요. 연결되지 않은 그래프에는 신장 트리가 없습니다.

10.5 무엇을 언제 쓰나

	크루스칼	프림
접근	간선 중심 (싼 것부터)	정점 중심 (트리 키우기)
필요 도구	정렬 + Union-Find	우선순위 큐(또는 배열)
시간	O(E log E)	O(V²) 또는 O(E log V)
유리한 상황	간선이 적을 때(희소)	간선이 많을 때(밀집)
그래프 표현	간선 목록	인접 행렬/리스트

그리고 마지막으로 꼭 짚고 가야 할 것이 있습니다.

MST는 최단 경로가 아닙니다.

MST는 “전체를 연결하는 비용의 합”을 최소화할 뿐, 두 특정 지점 사이의 거리를 최소화하지는 않습니다. 이 예제의 그래프에서 직접 확인했습니다.

$ ./mst_vs_sp
원래 그래프에서 B동->D동 최단: 5 (B-D 직행 5)   MST 로는 B-C-E-D = 2+4+1 = 7

B동에서 D동으로 가는 최단 경로는 직행 5억짜리 길입니다. 그런데 크루스칼은 이 간선을 “사이클!”이라며 거부했습니다. MST만 따라가면 B → C → E → D 로 7이 됩니다. MST에서 버린 간선이 최단 경로의 일부일 수 있는 것입니다. 수도관 공사비를 최소화하는 것과 물이 흐르는 거리를 최소화하는 것은 다른 문제입니다.

문제를 잘못 매칭하면 알고리즘은 완벽하게 동작하면서 엉뚱한 답을 내놓습니다. “연결 비용 최소”와 “이동 거리 최소”는 다른 문제라는 것을 기억하세요.

11. 실습 프로젝트

projects/ 폴더에는 이번 주 알고리즘을 실제 시스템처럼 묶은 세 프로그램이 있습니다. 각 프로그램의 구조와 핵심 함수를 정리합니다. 전체 코드는 해당 .c 파일을 열어 확인하세요. 출력은 모두 실제 실행 결과입니다.

$ cd week14
$ make                          # 전체 빌드
$ ./build/gps_navigation        # 또는 social_network, network_router

프로젝트 1: GPS 내비게이션 (gps_navigation.c)

대한민국 주요 도시 15개, 도로 23개의 지도에서 실제 내비처럼 경로를 안내합니다.

#define V 15
static const char *city[V] = {
    "서울", "인천", "수원", "춘천", "강릉", "대전", "청주", "전주",
    "광주", "여수", "대구", "포항", "울산", "부산", "창원",
};

typedef struct AdjNode {
    int vertex, km, minutes;     /* 거리와 시간, 두 가중치를 함께! */
    struct AdjNode *next;
} AdjNode;

void      add_road(int u, int v, int km, int minutes);
void      build_map(void);
void      heap_push(MinHeap *h, int dist, int vertex);     /* 12주차 최소 힙 */
HeapItem  heap_pop(MinHeap *h);
void      dijkstra(int start, int use_time, int dist[], int parent[]);
int       build_route(const int parent[], int dest, int route[]);
void      navigate(int from, int to);
int       find_city(const char *name_str);

경로 탐색

업그레이드 1, 힙 기반 다익스트라. 예제의 O(V²) 버전을 12주차 최소 힙을 써서 O(E log V) 로 올렸습니다. 핵심은 “확정 정점 고르기”를 선형 탐색에서 힙 pop 으로 바꾼 것입니다.

    HeapItem it = heap_pop(&heap);
    if (done[it.vertex]) continue;   /* 낡은 항목은 버린다 */

이 한 줄이 지연 삭제(lazy deletion) 기법입니다. 거리가 갱신될 때마다 힙에 새 항목을 넣기 때문에 같은 정점이 힙에 여러 번 들어갑니다. 힙에서 특정 항목을 찾아 고치는 것은 비싸므로, 그냥 새로 넣고 꺼낼 때 이미 확정된 것이면 버리는 방식입니다. 3.3절 반복문 DFS에서 본 “일단 넣고 꺼낼 때 거른다”와 같은 발상입니다.

업그레이드 2, 두 개의 가중치. 간선 하나에 km 과 minutes 를 함께 저장하고, dijkstra(start, use_time, ...) 의 플래그로 어느 쪽을 쓸지 고릅니다. 실제 내비의 “최단 거리 / 최소 시간” 옵션이 이것입니다.

$ ./build/gps_navigation
GPS 내비게이션 (도시 15개, 도로 23개)

================================================
 서울 -> 부산 경로 안내
================================================
[최단 거리 경로: 350km]
  출발: 서울
   경유: 청주 방면 120km
   경유: 대구 방면 110km
   도착: 부산 방면 120km

[최소 시간 경로: 4시간 20분] 서울 -> 청주 -> 대구 -> 부산
...
================================================
 강릉 -> 광주 경로 안내
================================================
[최단 거리 경로: 510km]
  출발: 강릉
   경유: 춘천 방면 100km
   경유: 서울 방면 75km
   경유: 수원 방면 35km
   경유: 대전 방면 120km
   경유: 전주 방면 85km
   도착: 광주 방면 95km

[최소 시간 경로: 6시간 40분] 강릉 -> 포항 -> 대구 -> 창원 -> 광주

(!) 거리 기준과 시간 기준의 경로가 다릅니다.
    고속도로는 멀어도 빠를 수 있으니까요 - 실제 내비와 동일!

같은 그래프인데 가중치만 바꿨더니 경로가 완전히 달라졌습니다. 거리 기준은 춘천과 서울을 거쳐 서쪽으로 돌고, 시간 기준은 포항과 대구를 거쳐 남쪽으로 갑니다. 고속도로가 멀어도 빠르다는 현실이 그대로 재현된 것입니다. 여러분이 내비에서 “최단 거리”를 골랐을 때 이상한 국도로 안내받은 경험이 있다면, 바로 이 차이입니다.

명령행 인자로 직접 검색할 수도 있습니다. 7주차에서 배운 argv 입니다.

$ ./build/gps_navigation 서울 여수
GPS 내비게이션 (도시 15개, 도로 23개)

================================================
 서울 -> 여수 경로 안내
================================================
[최단 거리 경로: 440km]
  출발: 서울
   경유: 청주 방면 120km
   경유: 대구 방면 110km
   경유: 창원 방면 80km
   도착: 여수 방면 130km

[최소 시간 경로: 5시간 30분] 서울 -> 청주 -> 대구 -> 창원 -> 여수

없는 도시를 넣으면 목록을 보여 주고 끝납니다.

$ ./build/gps_navigation 서울 제주
GPS 내비게이션 (도시 15개, 도로 23개)
도시를 찾을 수 없습니다. 가능한 도시:
  서울 인천 수원 춘천 강릉 대전 청주 전주 광주 여수 대구 포항 울산 부산 창원

확장 아이디어: 경유지 지정(다익스트라를 두 번 돌려 이어 붙이기), 도로 통제 반영(간선 제거 후 재계산), A* 휴리스틱(도시 좌표를 추가해 목적지 방향을 우선 탐색), 실시간 정체 반영(가중치 동적 변경)

프로젝트 2: 소셜 네트워크 분석 (social_network.c)

SNS의 그래프 기능 다섯 가지를 구현합니다. 사용자가 12명뿐이라 인접 행렬을 썼습니다. 2.4절의 기준 그대로입니다. “두 사람이 친구인가?”를 자주 묻고(friends[a][b] 한 칸), 정점이 적어 144칸이면 충분합니다.

#define V 12
static int friends[V][V];    /* 작은 규모라 인접 행렬이 간편 */
static int degree[V];

void add_friend(int a, int b);
int  mutual_friends(int a, int b, int result[]);          /* 함께 아는 친구 */
void recommend(int user);                                 /* 알 수도 있는 사람 */
int  separation(int a, int b, int path[], int *path_len); /* 촌수 = BFS */
int  find_communities(int comp[]);                        /* 연결 성분 */

소셜 그래프 분석

$ ./build/social_network
소셜 네트워크 분석 (사용자 12명)
=====================================

=== 친구 목록 ===
  민준(2명): 서연 도윤
  서연(4명): 민준 도윤 지우 하준
  ...
  소율(0명):

=== 인플루언서 랭킹 (친구 수) ===
  1위: 서연 (4명)
  2위: 하준 (4명)
  3위: 지우 (3명)

=== 촌수 계산 (BFS) ===
  민준 - 유나: 4다리 (민준->서연->하준->시우->유나)
  민준 - 아린: 3다리 (민준->서연->지우->아린)
  민준 - 은우: 연결 안 됨 (다른 세계!)
  민준 - 소율: 연결 안 됨 (다른 세계!)

[민준님, 알 수도 있는 사람]
  하준 (함께 아는 친구 2명: 서연, 도윤)
  지우 (함께 아는 친구 1명: 서연)

[유나님, 알 수도 있는 사람]
  하준 (함께 아는 친구 1명: 시우)
  아린 (함께 아는 친구 1명: 시우)

=== 커뮤니티 탐지 (연결 성분) ===
  그룹 1: 민준 서연 도윤 지우 하준 아린 시우 유나
  그룹 2: 은우 예나 건우
  그룹 3: 소율

다섯 기능이 각각 이번 주 어느 개념에 대응하는지 보세요.

기능	알고리즘	절
함께 아는 친구	두 사람의 이웃 집합의 교집합	2절 (표현)
알 수도 있는 사람	공통 친구 수로 비친구 랭킹	2절 + 정렬
촌수	BFS 최단 거리 + parent 경로 복원	4절
인플루언서	차수 랭킹	1절 (용어)
커뮤니티	연결 성분 (DFS/BFS)	3.6절

“알 수도 있는 사람”이 이 프로젝트의 백미입니다. 원리는 놀랍도록 단순합니다. 아직 친구가 아닌 사람 중, 공통 친구가 많은 순으로 추천하는 것입니다. 민준의 친구는 서연과 도윤인데, 하준은 그 둘 모두와 친구라 1순위로 추천됩니다. 여러분이 페이스북이나 인스타그램에서 보는 그 기능의 가장 기본적인 형태입니다(실제 서비스는 여기에 관심사, 위치, 활동 패턴 등 수십 가지 신호를 더합니다).

민준 - 은우: 연결 안 됨 (다른 세계!) 도 의미가 있습니다. BFS가 dist = -1 을 반환한 경우, 즉 연결 성분이 다르다는 뜻입니다. “케빈 베이컨의 6단계 법칙”은 같은 성분 안에서만 성립한다는 것을 보여 주는 사례입니다. 소율은 친구가 0명이라 혼자서 그룹 3입니다. 3.6절의 외톨이 정점 7과 같습니다.

확장 아이디어: 친구의 친구까지 가중치를 둔 추천 점수, 매개 중심성(모든 최단 경로에 자주 등장하는 사람 = 다리 역할), 파일에서 관계 로드(9주차), 정점 수를 늘려 인접 리스트로 전환

프로젝트 3: 네트워크 라우팅 시뮬레이터 (network_router.c)

인터넷 라우터의 링크 상태 라우팅(OSPF 프로토콜의 기반)을 시뮬레이션합니다.

#define V 7
static int link[V][V];               /* 링크 비용 행렬 (0 = 링크 없음) */

typedef struct {
    int next_hop[V];                 /* 목적지별 '다음 홉'만 저장! */
    int cost[V];
} RouteTable;

void set_link(int a, int b, int cost);
void dijkstra(int start, int dist[], int parent[]);
void build_table(int self, RouteTable *rt);       /* 자신 기준 다익스트라 */
void print_table(int self, const RouteTable *rt);
void send_packet(RouteTable table[], int src, int dst);
void rebuild_all(RouteTable table[]);             /* 장애 후 전체 재계산 */

동작은 이렇습니다.

1. 각 라우터가 네트워크 전체 지도를 공유한다
2. 각자 자신을 출발점으로 다익스트라를 돌려 라우팅 테이블을 만든다
3. 패킷은 홉마다 그 라우터의 테이블을 보고 다음 홉으로 전달된다

$ ./build/network_router
네트워크 라우팅 시뮬레이터 (링크 상태 방식)
=====================================
토폴로지:
  R1 --1-- R2 --2-- R3
   |        |        |
   4        1        3
   |        |        |
  R4 --2-- R5 --2-- R6 --1-- R7

[R1의 라우팅 테이블]
  목적지  다음홉  비용
  R2      R2      1
  R3      R2      3
  R4      R4      4
  R5      R2      2
  R6      R2      4
  R7      R2      5
...
>>> 패킷 전송: R1 -> R7
    R1 => R2 => R5 => R6 => R7  (도착! 4홉, 총 비용 5)

=====================================
!! 장애 발생: R5-R6 링크 절단 !!
=====================================

(1) 테이블 갱신 전에 패킷을 보내면? 옛 정보로 전달 시도...
    실제 네트워크에서 잠깐의 '수렴 시간' 동안 벌어지는 일!

(2) 모든 라우터가 다익스트라 재실행 (수렴 완료)

[R1의 라우팅 테이블]
  목적지  다음홉  비용
  R2      R2      1
  R3      R2      3
  R4      R4      4
  R5      R2      2
  R6      R2      6
  R7      R2      7

=== 장애 후 같은 패킷 다시 전송 ===

>>> 패킷 전송: R1 -> R7
    R1 => R2 => R3 => R6 => R7  (도착! 4홉, 총 비용 7)

이 프로젝트의 핵심 통찰은 라우팅 테이블의 구조입니다. 라우터는 전체 경로를 기억하지 않습니다. 목적지별로 “다음 홉” 하나만 기억합니다. R1의 테이블에서 R7로 가는 줄은 “일단 R2로 보내라”가 전부입니다.

왜 그럴까요? 전체 경로를 들고 있으면 경로가 바뀔 때마다 전부 갱신해야 하고, 중간 라우터가 더 좋은 길을 알고 있어도 쓸 수 없습니다. “일단 다음 한 걸음만 책임지고, 그다음은 거기 있는 라우터가 판단한다”는 분산된 책임이 인터넷 확장성의 비결입니다. 전 세계 라우터 누구도 인터넷 전체 경로를 알지 못하는데도 패킷이 지구 반대편까지 도착하는 이유입니다. 4절의 parent[] 배열이 “직전 정점 하나만” 기억하는 것과 같은 발상이기도 합니다.

장애 시나리오가 하이라이트입니다. R5-R6 링크가 끊기자 모든 라우터가 다익스트라를 다시 돌려 R2 → R3 → R6 우회로를 찾아냈습니다. 비용은 5에서 7로 늘었지만 패킷은 도착합니다. 이 재계산이 끝날 때까지의 시간을 수렴 시간(convergence time) 이라고 부르고, 그동안은 옛 정보로 패킷이 잘못 전달될 수 있습니다. 예제가 (1) 테이블 갱신 전에 패킷을 보내면? 으로 그 순간을 재현하는 이유입니다. 실제 인터넷에서도 장애 직후 몇 초간 통신이 불안정한 이유가 이것입니다. 21주차 네트워크 프로그래밍에서 이 위에 소켓을 얹습니다.

확장 아이디어: 링크 비용 동적 변경(혼잡도 반영), 거리 벡터 방식(RIP)으로 바꿔 비교, 라우팅 루프 상황 만들어 보기, 홉 수 제한(TTL) 추가

12. 자주 하는 실수와 함정

이번 주에 직접 밟아 본 함정들을 정리합니다. 괄호 안이 실험으로 확인한 절입니다.

1. visited 없이 그래프 순회. (3.4절) 재귀는 0 3 0 3 ... 을 반복하다 스택이 넘쳐 세그멘테이션 오류, 반복문은 스택 배열이 넘쳐 세그멘테이션 오류. 사이클이 하나만 있어도 반드시 죽습니다.

2. 무방향 간선을 한쪽만 추가. (2.5절) 오류 없이 결과가 반쪽만 나옵니다. 탐색 결과가 이상하면 add_edge 부터 의심하세요.

3. 그래프 구조체를 초기화하지 않음. (2.6절) 경고 없이 컴파일되고 실행하자마자 죽습니다. = {{0}} 또는 memset.

4. 깊은 그래프에 재귀 DFS. (3.5절) 8MB 스택은 이 예제 기준 약 26만 단계에서 끝납니다. 정점이 수십만 개를 넘을 수 있으면 반복문 버전.

5. BFS 방문 표시를 꺼낼 때 하기. (4.3절) 완전 그래프 8정점에서 큐 삽입이 8회 → 29회. 큐 크기 V로는 넘칩니다.

6. 음수 간선에 다익스트라. (6.4절) 조용히 틀린 답. 음수가 보이면 벨만-포드.

7. INF 에 INT_MAX 를 쓰고 덧셈하기. (8.4절) 거리표가 −21억으로 채워집니다. -fsanitize=undefined 가 위치를 알려 줍니다.

8. 플로이드-워셜 루프 순서. (8.3절) 예제 그래프에서는 우연히 맞고, 0→3→2→1 에서 “도달 불가”로 틀립니다. k가 반드시 가장 바깥.

9. 위상 정렬에서 진입 차수 원본 훼손. (5.2절) 두 번째 호출부터 엉뚱한 답. 복사본을 쓰세요.

10. qsort 비교 함수에서 뺄셈. (10.2절) INT_MAX - (-1) 이 음수. (a > b) - (a < b).

11. MST와 최단 경로 혼동. (10.5절) B동-D동 직행 5를 “사이클”로 버리고 MST 경로는 7. 다른 문제, 다른 알고리즘.

12. 그래프 메모리 해제 잊기. 인접 리스트는 노드마다 malloc 을 합니다. graph_free 를 꼭 호출하고 make memcheck 로 확인하세요. 이번 주 예제 12개는 전부 누수 0입니다.

13. 연습 문제

기본 문제

1. 간선 수 세기: 인접 리스트 그래프의 간선 수를 세는 함수를 작성하세요. 무방향 그래프에서는 차수 합의 절반이 간선 수입니다. 1절의 성질을 코드로 확인하는 문제입니다.
2. 이분 그래프 판정: BFS로 정점을 두 색으로 칠하되 인접한 정점은 다른 색이어야 합니다. 모순 없이 칠할 수 있으면 이분 그래프입니다.
3. 미로 최단 경로: 2차원 격자 미로(# 은 벽, . 은 길)에서 출발점부터 도착점까지 최단 경로를 BFS로 구하세요. 격자의 각 칸이 정점, 상하좌우가 간선입니다. 5주차의 미로 프로젝트를 BFS로 다시 만드는 것입니다.
4. DFS 위상 정렬: 5절의 Kahn 방식 대신 DFS로 위상 정렬을 구현하세요. 힌트: 자식을 다 처리한 뒤 스택에 쌓고, 마지막에 스택을 비웁니다.
5. 그래프 복사: 인접 리스트 그래프를 깊은 복사하는 함수를 작성하세요. 8주차의 얕은 복사와 깊은 복사 이야기를 떠올리세요.

심화 문제

6. 사이클 찾아 출력하기: 사이클이 있는지만이 아니라 어떤 사이클인지 출력하세요. DFS 중 “현재 경로에 있는 정점”을 다시 만나면 사이클입니다.
7. 다익스트라 힙 버전: 예제의 O(V²) 다익스트라를 12주차 최소 힙으로 O(E log V) 로 개선하고, 정점 수를 1,000, 10,000, 100,000으로 늘려 가며 시간을 재 보세요. 어디서부터 차이가 나기 시작하나요?
8. 모든 최단 경로 세기: 출발점에서 각 정점까지 최단 경로가 몇 개인지 세세요. 4.2절의 지하철 그래프에서 7번까지는 2개입니다. BFS 중 dist[v] == dist[u] + 1 이면 경로 수를 더합니다.
9. A* 알고리즘: GPS 프로젝트에 도시 좌표를 추가하고, 목적지까지의 직선 거리를 힌트로 쓰는 A* 를 구현하세요. 다익스트라보다 탐색하는 정점 수가 얼마나 줄어드나요?
10. 강한 연결 성분(SCC): 방향 그래프에서 “서로 오갈 수 있는” 정점 덩어리를 찾으세요(코사라주 또는 타잔 알고리즘). 웹페이지 링크 구조 분석에 쓰입니다.

마치며

이번 주에 배운 것을 정리합니다.

• 표현: 현실 그래프는 희소하다 → 기본값은 인접 리스트. 같은 그래프라도 작업에 따라 승자가 바뀐다(2.4절). 알고리즘에 따라 행렬이나 간선 목록도
• 탐색: BFS(큐) = 최단 거리, DFS(스택) = 존재와 구조. visited 는 필수이고 없으면 반드시 죽는다
• 위상 정렬: 의존성 순서 + 덤으로 사이클 감지 (make 가 하는 그 일)
• 최단 경로: 상황별 3형제. 다익스트라(기본), 벨만-포드(음수 + 사이클 감지), 플로이드-워셜(모든 쌍)
• 완화(relax): 세 최단 경로 알고리즘의 공통 심장. 차이는 “어떤 순서로 몇 번 완화하느냐”뿐
• Union-Find: 경로 압축 + 랭크로 사실상 O(1). 없으면 1.5초, 있으면 0.0ms. union 의 반환값이 사이클 감지기
• MST: 크루스칼(간선 정렬 + Union-Find) vs 프림(트리 키우기). 둘 다 탐욕법인데 둘 다 최적. 그러나 최단 경로는 아니다

그리고 오늘로 Part 2의 자료구조 여정이 완성되었습니다. 배열과 리스트(10주) → 스택과 큐(11주) → 트리와 힙(12주) → 해시(13주) → 그래프(14주). 이제 여러분의 도구함에는 어떤 데이터든 담아낼 그릇이 다 갖춰졌습니다.

이번 주가 특별했던 이유가 하나 더 있습니다. 새 자료구조를 거의 배우지 않았다는 것입니다. 그래프 알고리즘의 재료는 전부 이전 주차의 것이었습니다. 큐, 스택, 힙, 연결 리스트, 배열, 정렬. 새로웠던 건 그것들을 조합하는 방식뿐입니다. 앞으로 여러분이 만날 대부분의 “어려워 보이는 알고리즘”이 이런 식입니다. 기본기가 탄탄하면 새 알고리즘은 조합의 문제가 됩니다.

그리고 이번 주에 가장 강조하고 싶은 것은 일부러 망가뜨려 보는 습관입니다. visited 를 빼 보고, 루프 순서를 바꿔 보고, INF 에 INT_MAX 를 넣어 봤습니다. 그래프 알고리즘의 버그는 컴파일러가 잡아 주지 않고, 답이 그럴싸하게 나오는 경우가 많습니다. 어떻게 틀리는지를 미리 봐 둔 사람만이 나중에 자기 코드의 이상한 결과를 알아볼 수 있습니다.

남은 3주(15~17주)는 알고리즘입니다. 이 그릇들 위에서 데이터를 다루는 기술을 배웁니다. 다음 주는 정렬과 검색입니다. 퀵 정렬은 왜 빠른가, 언제 배신하는가, 오늘 잠깐 본 qsort 의 비교 함수와 “안정 정렬”은 무엇인가, 그리고 “쉬워 보이는” 이진 탐색의 무서운 함정까지. 이미 힙 정렬(12주차)을 만들어 본 여러분에겐 어렵지 않을 겁니다.

수고하셨습니다. 그래프는 처음엔 용어가 많아 부담스럽지만, 한 번 익숙해지면 세상의 문제들이 정점과 간선으로 보이기 시작합니다. 그때가 정말 재미있어지는 순간입니다.

체크리스트

이번 주차를 마쳤다면 스스로 확인해 보세요. 각 항목을 설명할 수 있으면 체크합니다.

• [ ] 정점, 간선, 차수, 경로, 사이클, 연결 성분을 정확히 설명할 수 있다
• [ ] 방향/무방향, 가중치/무가중치의 차이와 그에 따른 알고리즘 선택을 안다
• [ ] 인접 행렬과 리스트의 메모리 차이를 계산할 수 있다 (V² vs V + 2E). 그리고 실제 메모리가 계산과 왜 다른지 안다
• [ ] 무방향 간선을 양쪽에 넣어야 하는 이유를 실험 결과로 설명할 수 있다
• [ ] visited 배열이 트리 순회에는 없고 그래프에는 필수인 이유를 알고, 없으면 어떻게 죽는지 봤다
• [ ] 재귀 DFS와 반복문 DFS를 둘 다 구현할 수 있고, 재귀의 깊이 한계를 안다
• [ ] 반복문 DFS의 스택과 BFS의 큐 내용을 단계별로 적을 수 있다
• [ ] DFS로 연결 성분(섬)을 셀 수 있다
• [ ] BFS가 무가중치 최단 경로인 이유를 설명할 수 있다
• [ ] BFS에서 방문 표시를 큐에 넣을 때 하는 이유를 숫자로 말할 수 있다
• [ ] parent 배열로 경로를 복원할 수 있다
• [ ] Kahn 위상 정렬을 구현하고 사이클을 감지할 수 있다. make 의 순환 의존성 메시지를 봤다
• [ ] 완화(relaxation)가 무엇이고 세 알고리즘의 공통점인지 안다
• [ ] 다익스트라의 거리표를 라운드별로 채울 수 있고, 음수 간선에서 어떻게 틀리는지 봤다
• [ ] 벨만-포드가 V − 1 라운드면 충분한 이유와, 간선 순서가 라운드 수에 주는 영향을 안다
• [ ] 음수 사이클 감지 방법(V번째 라운드)과 그 실무 용도를 안다
• [ ] 플로이드-워셜에서 k가 바깥 루프여야 하는 이유를 알고, 틀리는 그래프를 만들 수 있다
• [ ] INF 에 INT_MAX 를 쓰면 안 되는 경우를 구분하고, 실제로 어떻게 깨지는지 봤다
• [ ] Union-Find의 경로 압축을 구현하고, 최적화 유무의 시간 차이를 안다
• [ ] 크루스칼이 사이클을 피하는 원리(union 반환값)를 안다
• [ ] 프림과 다익스트라의 코드 차이(갱신 식)를 말할 수 있다
• [ ] MST와 최단 경로가 다른 문제임을 예제 그래프의 B동-D동으로 설명할 수 있다
• [ ] 세 프로젝트를 빌드하고 make memcheck 로 누수 0을 확인했다
• [ ] (도전) GPS에 경유지 기능을, SNS에 매개 중심성을 추가해 봤다

---

참고 자료

• CLRS(Introduction to Algorithms) Chapter 22-25 (그래프 알고리즘 전권)
• VisuAlgo — 그래프 탐색 / 최단 경로 / MST 시각화
• Dijkstra 원 논문 이야기 (1959, 카페에서 20분 만에 구상)
• OSPF 프로토콜 개요 (RFC 2328)
• 다음 주차: 15주차 정렬과 검색 알고리즘