왜 트리와 그래프를 구현 수준까지 다루는가

04편에서 트리는 “계층 구조를 표현하는 자료구조”, 그래프는 “임의의 관계를 표현하는 자료구조”라고 개념을 정리했다. 13편에서는 배열·스택·큐·재귀를 실제 C 코드로 구현하며 개념을 코드로 옮기는 훈련을 했다. 이 편은 그 연장선에서 트리와 그래프를 포인터·배열로 실제로 구현하고, 순회·탐색 알고리즘이 방문하는 노드 순서를 한 단계씩 표로 추적한다.

독학사 통합프로그래밍 시험에서 트리·그래프 문제는 “이 트리를 전위 순회하면 어떤 순서로 출력되는가”, “이 그래프를 DFS로 탐색하면 방문 순서는?”처럼 결과를 손으로 계산시키는 형태가 압도적으로 많다. 개념만 알아서는 풀 수 없고, 알고리즘을 한 단계씩 직접 실행해 보는 훈련이 필요하다.

이진 트리 구현: 노드와 포인터

이진 트리(binary tree)는 각 노드가 최대 두 개의 자식(왼쪽·오른쪽)을 가지는 트리다. 07편의 연결리스트 노드가 다음 노드 포인터 하나만 가졌다면, 이진 트리 노드는 왼쪽 자식·오른쪽 자식, 두 개의 포인터를 가진다.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct 노드 {
    int data;
    struct 노드 *left;
    struct 노드 *right;
} 노드;
 
노드 *노드생성(int value) {
    노드 *n = (노드 *)malloc(sizeof(노드));
    n->data = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

malloc(08편에서 다룬 동적 메모리 할당 함수)으로 힙(heap) 영역에 노드를 하나씩 만들고, left·right 포인터로 부모-자식 관계를 연결한다. 아래 트리를 코드로 직접 구성해 본다.

int main(void) {
    노드 *root = 노드생성(10);
    root->left = 노드생성(5);
    root->right = 노드생성(15);
    root->left->left = 노드생성(3);
    root->left->right = 노드생성(7);
    return 0;
}

root->left->left처럼 포인터를 연속으로 따라가는 표현은 “root의 왼쪽 자식의 왼쪽 자식”을 가리킨다. 화살표(->)가 이어질수록 트리에서 더 깊은 레벨로 내려간다는 점을 기억한다.

트리 순회: 전위·중위·후위

순회(traversal)는 트리의 모든 노드를 정해진 규칙에 따라 한 번씩 방문하는 것이다. 이진 트리의 세 가지 기본 순회는 루트를 방문하는 시점만 다르다.

void 전위순회(노드 *n) {
    if (n == NULL) return;
    printf("%d ", n->data);
    전위순회(n->left);
    전위순회(n->right);
}
 
void 중위순회(노드 *n) {
    if (n == NULL) return;
    중위순회(n->left);
    printf("%d ", n->data);
    중위순회(n->right);
}
 
void 후위순회(노드 *n) {
    if (n == NULL) return;
    후위순회(n->left);
    후위순회(n->right);
    printf("%d ", n->data);
}

앞서 만든 트리(루트 10, 왼쪽 서브트리 5-3-7, 오른쪽 서브트리 15)에 세 순회를 각각 호출한 결과다.

전위: 10 5 3 7 15
중위: 3 5 7 10 15
후위: 3 7 5 10 15

전위 순회 한 단계씩 추적(재귀 호출이 어떤 순서로 printf를 실행하는지 13편의 스택 프레임 방식으로 따라간다):

쉽게 말하면: 전위 순회는 “일단 나부터 소개하고 왼쪽 자식들, 그다음 오른쪽 자식들을 소개한다”는 규칙이다. 중위는 “왼쪽 자식들을 먼저 다 소개한 다음 나를 소개하고, 마지막으로 오른쪽 자식들”이다. 이 트리가 이진 탐색 트리(다음 절)라면 중위 순회 결과가 항상 오름차순 정렬이 된다는 성질이 매우 중요하다.

자주 틀리는 점: 중위 순회의 이름(“중위”)을 “가운데 자식을 먼저 방문한다”로 오해하는 경우가 있다. 이진 트리에는 “가운데 자식”이 없다. 중위는 루트를 왼쪽과 오른쪽 사이(중간)에 방문한다는 뜻이지, 자식의 위치와는 무관하다.

이진 탐색 트리: 정렬된 순서를 유지하는 트리

이진 탐색 트리(Binary Search Tree, BST)는 모든 노드에 대해 “왼쪽 서브트리의 모든 값 < 자신의 값 < 오른쪽 서브트리의 모든 값”이 성립하는 이진 트리다. 이 규칙 덕분에 값을 찾을 때 트리의 절반씩 후보를 제외하며 내려갈 수 있다(15편의 이진 탐색과 원리가 같다).

노드 *삽입(노드 *root, int value) {
    if (root == NULL) return 노드생성(value);
    if (value < root->data) {
        root->left = 삽입(root->left, value);
    } else {
        root->right = 삽입(root->right, value);
    }
    return root;
}

값 10, 5, 15, 3, 7을 순서대로 삽입하면 앞서 그린 트리와 정확히 같은 모양이 만들어진다. 삽입(root, 3)을 예로 한 단계씩 추적한다.

이 BST를 중위 순회하면 3 5 7 10 15로, 삽입 순서와 무관하게 항상 오름차순이 나온다는 점이 BST의 핵심 성질이다.

그래프 표현: 인접 행렬 vs 인접 리스트

그래프(graph)는 정점(vertex, 노드)과 그 사이를 잇는 간선(edge)의 집합이다. 트리와 달리 순환(cycle)이 있을 수 있고 부모-자식 같은 계층 관계도 없다. 그래프를 코드로 표현하는 방법은 크게 두 가지다.

인접 행렬(adjacency matrix)은 정점 개수만큼의 2차원 배열로, graph[i][j]가 1이면 정점 i와 j 사이에 간선이 있다는 뜻이다.

int graph[4][4] = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0}
};

인접 리스트(adjacency list)는 각 정점마다 “나와 연결된 정점들의 목록”을 연결리스트나 배열로 저장한다.

typedef struct 간선노드 {
    int vertex;
    struct 간선노드 *next;
} 간선노드;
 
간선노드 *adjList[4]; /* adjList[i]는 정점 i와 연결된 정점들의 연결리스트 머리 */

자주 틀리는 점: “인접 리스트가 항상 더 좋다”는 생각은 틀렸다. 정점 수가 적고 간선이 조밀한(dense) 그래프에서는 인접 행렬의 O(1) 연결 확인이 더 유리할 수 있다. 어떤 표현이 나은지는 그래프의 밀도(간선이 얼마나 촘촘한가)에 달려 있다는 점을 시험은 “상황에 따라”라는 형태로 묻는다.

DFS: 깊이 우선 탐색과 스택

DFS(Depth-First Search, 깊이 우선 탐색)는 한 정점에서 갈 수 있는 만큼 깊이 들어갔다가, 더 갈 곳이 없으면 되돌아와(백트래킹) 다른 경로를 탐색하는 방법이다. 13편에서 다룬 스택(또는 재귀 호출 스택)을 이용해 구현한다.

int visited[4] = {0, 0, 0, 0};
 
void dfs(int graph[4][4], int v) {
    visited[v] = 1;
    printf("%d ", v);
    for (int next = 0; next < 4; next++) {
        if (graph[v][next] == 1 && visited[next] == 0) {
            dfs(graph, next);
        }
    }
}

앞서 정의한 그래프(정점 0-1, 0-2, 1-3, 2-3 간선)에서 dfs(graph, 0)을 호출했을 때의 방문 순서를 단계별로 추적한다.

0 1 3 2

BFS: 너비 우선 탐색과 큐

BFS(Breadth-First Search, 너비 우선 탐색)는 현재 정점에서 가까운 정점부터 순서대로 탐색한다. DFS가 스택(또는 재귀)을 쓰는 것과 달리, BFS는 13편에서 다룬 큐(FIFO)를 사용한다.

void bfs(int graph[4][4], int start) {
    int visited[4] = {0, 0, 0, 0};
    int queue[4], front = 0, rear = 0;
 
    visited[start] = 1;
    queue[rear++] = start;
 
    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);
        for (int next = 0; next < 4; next++) {
            if (graph[v][next] == 1 && visited[next] == 0) {
                visited[next] = 1;
                queue[rear++] = next;
            }
        }
    }
}

같은 그래프에서 bfs(graph, 0)을 호출했을 때 큐 상태를 단계별로 추적한다.

0 1 2 3

같은 그래프인데도 DFS는 0 1 3 2, BFS는 0 1 2 3으로 방문 순서가 다르다는 점이 이 두 알고리즘의 가장 중요한 차이다.

핵심 정리

• 이진 트리 노드는 왼쪽·오른쪽 두 포인터를 가지며, 전위(루트-왼쪽-오른쪽)·중위(왼쪽-루트-오른쪽)·후위(왼쪽-오른쪽-루트) 순회는 루트를 방문하는 시점만 다르다.
• 이진 탐색 트리는 왼쪽 서브트리 < 자신 < 오른쪽 서브트리 규칙을 지키며, 중위 순회 결과가 항상 오름차순이 된다.
• 그래프는 인접 행렬(O(1) 연결 확인, O(V²) 메모리)과 인접 리스트(O(V+E) 메모리, 희소 그래프에 유리)로 표현할 수 있다.
• DFS는 스택(재귀)으로 깊이 우선, BFS는 큐로 너비 우선 탐색하며 같은 그래프에서도 방문 순서가 서로 다르다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 4단계 통합프로그래밍의 평가영역과 출제 범위를 확인할 수 있는 공식 사이트.