C++ 알고리즘) 트리, 그래프 및 백트래킹

트리

트리(Tree)는 계층적인 구조를 표현하는 아주 중요한 자료구조다. 선형 구조(배열, 리스트)와 달리 부모-자식 관계를 가지는 비순환 그래프의 일 형태다.

---

1. 트리의 주요 개념

• 노드(Node): 데이터를 저장하는 기본 단위.
• 루트(Root): 트리의 최상단 노드 (부모가 없는 노드).
• 리프(Leaf/Terminal): 자식이 없는 최하단 노드.
• 차수(Degree): 각 노드가 가진 자식의 수.
• 깊이(Depth): 루트에서 특정 노드까지 도달하기 위해 거치는 간선의 수.
• 높이(Height): 루트에서 가장 먼 리프 노드까지의 거리.

---

2. C++에서의 트리 구현 (이진트리 기준)

가장 많이 쓰이는 이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식(Left, Right)만 가질 수 있다.

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

배열로 구현

// 배열로 구성된 이진 트리에서 부모-자식 관계를 출력하는 예제
// - 인덱스 1부터 시작
// - 왼쪽 자식: index * 2
// - 오른쪽 자식: index * 2 + 1

#include <iostream>
using namespace std;

int main() {
    const int SIZE = 16;
    int tree[SIZE] = {0};

    // 트리 구성
    tree[1] = 1;  // 루트
    tree[2] = 2;
    tree[3] = 3;
    tree[4] = 4;
    tree[5] = 5;
    tree[6] = 6;
    tree[7] = 7;

    // 부모-자식 관계 출력
    for (int i = 1; i < SIZE; ++i) {
        if (tree[i] != 0) {
            int left = i * 2;
            int right = i * 2 + 1;

            cout << "부모 노드 (" << tree[i] << "): ";
            if (left < SIZE && tree[left] != 0)
                cout << "왼쪽 자식 -> " << tree[left] << " ";
            if (right < SIZE && tree[right] != 0)
                cout << "오른쪽 자식 -> " << tree[right];
            cout << endl;
        }
    }

    return 0;
}

/*
출력결과:
부모 노드 (1): 왼쪽 자식 -> 2 오른쪽 자식 -> 3
부모 노드 (2): 왼쪽 자식 -> 4 오른쪽 자식 -> 5
부모 노드 (3): 왼쪽 자식 -> 6 오른쪽 자식 -> 7
부모 노드 (4): 
부모 노드 (5): 
부모 노드 (6): 
부모 노드 (7): 
*/

 

인접리스트로 구현

// 목적: 인접 리스트 방식으로 트리를 표현하고 출력하는 예제 (노드 추가 버전)
// 동작: 각 노드는 자식 노드를 리스트로 저장하며, 출력 시 부모 -> 자식 관계를 보여줌

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 9; // 노드 개수 (0부터 8까지 총 9개 노드)
    vector<vector<int>> tree(n);

    // 트리 간선 정보 추가 (0을 루트로 가정)
    tree[0].push_back(1);
    tree[0].push_back(2);
    tree[1].push_back(3);
    tree[1].push_back(4);
    tree[2].push_back(5);
    tree[2].push_back(6);
    tree[3].push_back(7);
    tree[4].push_back(8);

    // 트리 출력
    for (int i = 0; i < n; ++i) {
        cout << i << " -> ";
        for (int child : tree[i]) {
            cout << child << " ";
        }
        cout << endl;
    }

    return 0;
}

/*
출력결과
0 -> 1 2 
1 -> 3 4 
2 -> 5 6 
3 -> 7 
4 -> 8 
5 -> 
6 -> 
7 -> 
8 -> 
*/

---

3. 트리 탐색 (Traversal)

A. 깊이 우선 탐색 (DFS, Depth-First Search)

재귀나 스택을 사용하여 최대한 깊게 내려갔다가 돌아오는 방식이다. 방문 순서에 따라 세 가지로 나뉜다.

1. 전위 순회 (Pre-order): 루트 → 왼쪽 → 오른쪽
   • 트리 복사나 구조 파악에 유리하다.
2. 중위 순회 (In-order): 왼쪽 → 루트 → 오른쪽
   • 이진 탐색 트리(BST)에서 중위 순회를 하면 데이터를 오름차순으로 얻을 수 있다.
3. 후위 순회 (Post-order): 왼쪽 → 오른쪽 → 루트
   • 자식 노드를 먼저 처리해야 하는 트리 삭제나 수식 계산 등에 쓰인다.

B. 너비 우선 탐색 (BFS, Breadth-First Search)

큐(Queue)를 사용하여 같은 레벨(깊이)에 있는 노드들을 먼저 전부 방문하는 방식이다. 레벨 순서 순회(Level-order Traversal)라고도 부른다.

---

4. 탐색 예시 코드

void preOrder(Node* node) {
    if (node == nullptr) return;
    std::cout << node->data << " "; // 루트 방문
    preOrder(node->left);           // 왼쪽 서브트리
    preOrder(node->right);          // 오른쪽 서브트리
}

void inOrder(Node* node) {
    if (node == nullptr) return;
    inOrder(node->left);
    std::cout << node->data << " ";
    inOrder(node->right);
}

void postOrder(Node* node) {
    if (node == nullptr) return;
    postOrder(node->left);
    postOrder(node->right);
    std::cout << node->data << " ";
}

---

요약

• 구조: 부모-자식의 계층적 구조.
• DFS: 재귀를 이용해 깊게 탐색 (전위/중위/후위).
• BFS: 큐를 이용해 레벨별로 탐색.

---

그래프

트리(Tree)가 계층적인 '부모-자식' 관계라면, 그래프(Graph)는 조금 더 자유롭고 복잡한 '네트워크' 관계를 표현하는 자료구조다. 실생활에서는 지도(경로 찾기), SNS(친구 관계), 웹페이지의 링크 구조 등을 모델링할 때 사용된다.

---

1. 그래프의 구성 요소 및 특징

구성 요소

• 정점 (Vertex/Node): 데이터를 저장하는 점.
• 간선 (Edge): 정점과 정점을 잇는 선.
• 가중치 (Weight): 간선을 지나는 데 드는 비용(거리, 시간 등).

특징

• 방향성: 방향이 있는 유향 그래프(Directed)와 방향이 없는 무향 그래프(Undirected)로 나뉜다.
• 사이클: 시작점에서 다시 자기 자신으로 돌아오는 경로가 존재할 수 있다.
• 연결성: 모든 정점이 연결되어 있지 않을 수도 있다 (고립된 정점 가능).

2. 그래프의 구현 방식 (C++)

A. 인접 행렬 (Adjacency Matrix)

2차원 배열을 사용하여 연결 여부를 저장한다. adj [i][j] = 1이면 i에서 j로 가는 간선이 있다는 뜻이다.

• 장점: 두 정점의 연결 여부를 O(1)로 즉시 확인 가능.
• 단점: 정점이 V개일 때 V^2의 공간이 필요하므로 메모리 낭비가 심함.

B. 인접 리스트 (Adjacency List)

vector<int> adj [V]와 같이 각 정점마다 연결된 이웃 목록을 리스트로 관리한다.

• 장점: 실제 간선의 개수만큼만 메모리를 사용 (O(V+E)).
• 단점: 두 정점이 연결되었는지 확인하려면 리스트를 순회해야 함. (실무/코딩 테스트에서 주로 사용)

3. 그래프 탐색: DFS vs BFS

탐색의 핵심은 "방문한 노드를 다시 방문하지 않도록 visited 배열을 체크하는 것"이다.

깊이 우선 탐색 (DFS, Depth-First Search)

한 방향으로 갈 수 있을 때까지 깊게 가다가, 막히면 가장 최근 갈림길로 돌아와 다른 방향을 탐색한다.

• 원리: 스택(Stack) 또는 재귀(Recursion) 함수를 이용.
• 용도: 미로 찾기, 사이클 존재 여부 확인, 모든 경로 탐색.

너비 우선 탐색 (BFS, Breadth-First Search)

시작 정점에서 가까운 정점부터 차례대로 모두 방문한다.

• 원리: 큐(Queue)를 이용.
• 용도: 최단 경로(Shortest Path) 찾기 (가중치가 없는 그래프에서).

---

4. C++ 구현 예시 (인접 리스트 기준)

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

using namespace std;

vector<int> adj[10];
bool visited[10];

// DFS 구현 (재귀)
void dfs(int cur) {
    visited[cur] = true;
    cout << cur << " ";
    for (int next : adj[cur]) {
        if (!visited[next]) dfs(next);
    }
}

// BFS 구현 (큐)
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << " ";

        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}`

DFS와 BFS 중 무엇을 써야 할까요?

• 경로의 특징을 저장해야 하거나 모든 노드를 방문해야 한다면? -> DFS
• 최단 거리를 찾아야 하거나 타겟이 시작점 근처에 있다면? -> BFS

---

백트래킹

백트래킹(Backtracking)은 한마디로 "가보고 아니면 돌아오기" 전략이다. 모든 가능성을 탐색하는 완전 탐색(Brute-force)의 일종이지만, 중간에 '답이 될 가망이 없는 경로'를 미리 차단한다는 점에서 훨씬 똑똑한 알고리즘이다.

---

1. 백트래킹의 기본 구조

백트래킹은 보통 **재귀(Recursion)**를 이용해 구현하며, 상태 공간 트리(State Space Tree)를 탐색하는 방식이다.

표준 템플릿 (Pseudocode)

void backtrack(현재_상태) {
    // 1. 종료 조건 (해를 찾은 경우)
    if (is_solution(현재_상태)) {
        process_solution();
        return;
    }

    // 2. 다음 후보군 순회
    for (후보 : 모든_가능한_선택지) {
        if (is_promising(후보)) { // 3. 유망성 검사 (Pruning)
            make_choice(후보);    // 선택 진행
            backtrack(다음_상태); // 재귀 호출
            undo_choice(후보);    // 선택 취소 (상태 복구 - 핵심!)
        }
    }
}`

2. 효율성 핵심 메커니즘: 가지치기 (Pruning)

백트래킹의 성능은 "얼마나 빨리 탐색을 포기하느냐"에 달려 있다.

1. 유망성 판단 (Promising): 현재 노드에서 하위 노드로 내려갔을 때 해답이 나올 가능성이 있는지 체크한다.
2. 가지치기 (Pruning): 유망하지 않다고 판단되면 그 즉시 탐색을 중단하고 부모 노드로 돌아간다(Backtrack).
   • 예: N-Queen 문제에서 퀸을 놓으려는데 이미 같은 열에 다른 퀸이 있다면, 그 아래 단계는 더 볼 필요도 없이 취소한다.

---

3. 제약 충족 문제(CSP) 적용 전략

제약 충족 문제(Constraint Satisfaction Problem, 예: 스도쿠, N-Queen, 지도 색칠)에 백트래킹을 적용할 때는 아래 3가지 기법을 쓰면 성능이 폭발적으로 향상된다.

① 변수 선택 순서 (Variable Ordering)

• MRV(Minimum Remaining Values): 선택지가 가장 적은 칸부터 먼저 채운다. (예: 스도쿠에서 빈칸이 거의 다 채워진 행부터 공략)
• 일찍 실패를 발견할수록 탐색 범위가 좁아진다.

② 값 선택 순서 (Value Ordering)

• LCV(Least Constraining Value): 나중에 다른 변수들이 선택할 수 있는 자유를 최대한 방해하지 않는 값부터 선택한다.

③ 전방 확인 (Forward Checking)

• 현재 값을 선택했을 때, 아직 정해지지 않은 인접 변수들의 선택지가 아예 사라져 버리는지 미리 체크한다. 만약 하나라도 선택지가 0개가 된다면 즉시 가지치기를 수행한다.

---

4. 백트래킹 vs DFS

• DFS: 모든 노드를 방문하는 것이 목적이다. (그래프 탐색)
• Backtracking: 불필요한 경로를 차단하여 효율적으로 답을 찾는 것이 목적이다. 모든 노드를 가지 않는다.