[C++ - TIL] 그래프 탐색 알고리즘 - BFS의 체계적 이해와 위상 정렬의 기초

🎮 주제 : 그래프 탐색 알고리즘 - BFS의 체계적 이해와 위상 정렬의 기초

태그 : #C++ #알고리즘 #BFS #DFS #위상정렬 #진입차수 #진출차수 #자료구조

---

📌 학습 요약

• 너비 우선 탐색 (BFS) : **큐(Queue)**를 활용하여 시작 노드에서 가까운 노드부터 차례대로 방문하는 탐색 기법으로, 레벨 단위 탐색 및 최단 경로 문제 해결의 핵심 원리 파악
• 깊이 우선 탐색 (DFS) : 재귀나 스택을 활용하여 경로를 끝까지 파고드는 탐색 기법으로, 모든 경우의 수를 확인하거나 미로 탐색 등에 적합한 구조 이해
• 위상 정렬 (Topological Sort) 기초 : 노드 간의 우선순위가 있는 방향 그래프에서 순서를 나열하는 기법으로, 이를 위한 필수 개념인 차수(Degree) 정립
• 차수의 구분 : 노드로 들어오는 간선의 개수인 **진입 차수(In-degree)**와 나가는 간선의 개수인 **진출 차수(Out-degree)**를 표를 통해 시각적으로 분석

---

🛠 주요 코드 및 구현 상세

1. BFS (너비 우선 탐색) 핵심 로직

void bfs(T start) {
    queue<T> q;
    unordered_set<T> visited;

    // 1. 시작 노드 예약 및 방문 처리
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        // 2. 큐의 가장 앞(가까운 노드)을 꺼냄
        T temp = q.front();
        q.pop();
        cout << temp << " ";

        // 3. 현재 노드와 연결된 인접 노드 확인
        for (const auto& element : adjacencyList[temp]) {
            // 방문하지 않은 노드만 큐에 넣고 즉시 방문 처리
            if (visited.count(element) == 0) {
                visited.insert(element);
                q.push(element);
            }
        }
    }
}

2. 진입 차수와 진출 차수의 이해

• 그래프 예시 : A → B → C (방향 그래프)

노드 진입 차수 (In-degree) 진출 차수 (Out-degree) 역할 설명

A	0	1	시작점 (진입하는 선이 없음)
B	1	1	중간 경로
C	1	0	종착점 (나가는 선이 없음)

---

✅ 주요 문법 및 개념 정리

도구 / 개념 특징 활용 사례

queue<T>	선입선출 (FIFO) 구조	BFS 탐색 순서 유지
unordered_set	중복 허용 안 함, 해시 기반 탐색	O(1) 속도로 방문 여부(visited) 확인
진입 차수	나에게 들어오는 화살표 수	위상 정렬에서 작업 시작 가능 여부 판단
레벨 단위 탐색	인접 노드를 먼저 모두 방문	최단 거리(간선 개수 기준) 계산

💡 핵심 포인트 : 방문 처리(visited.insert)의 타이밍

• BFS에서는 노드를 큐에 넣을 때 바로 방문 처리를 해주는 것이 중요
• 큐에 들어있는 동안 다른 노드에 의해 중복해서 큐에 쌓이는 것을 방지하여 메모리와 연산의 효율성을 높일 수 있음

---

✨ 느낀 점

• BFS를 구현할 때 큐를 사용하여 '가까운 순서'대로 탐색이 보장되는 원리를 코드 흐름을 통해 명확히 체득함
• 단순히 알고리즘을 외우는 것이 아니라, 큐에 데이터가 쌓이고 빠지는 과정을 시각화해 보니 탐색의 선후 관계가 훨씬 잘 이해됨
• 진입 차수와 진출 차수를 직접 표로 그려보니, 왜 위상 정렬에서 "진입 차수가 0인 노드"부터 시작해야 하는지 논리적인 근거를 발견함
• visited.count()를 활용해 중복 방문을 막는 로직이 그래프 탐색의 성능과 안정성에 얼마나 큰 영향을 미치는지 다시금 깨달음