📚 DFS / BFS

📚 DFS / BFS

---

📚 DFS 와 BFS

• DFS = Depth Frist Search = 깊이 우선 탐색
• BFS = Breadth First Search = 너비 우선 탐색

그래프나 트리에서 데이터를 탐색하거나 순회하는 기본 알고리즘이다.

---

📚 DFS란?

• 깊이 우선 탐색
• 시간 복잡도 : (O(V+E))
• 공간 복잡도 : (O(H)) (H : 트리 높이)
• 하나의 경로를 끝까지 탐색한 뒤에야 다른 경로로 이동
• 구현 방법은 스택, 재귀 호출은 스택을 암묵적으로 사용하기 때문에, DFS는 일반적으로 재귀로 구현 되기도 한다.

---

🔎 DFS 특징

• 탐색 방식 : 노드 방문 > 다음 깊은 노드 방문 > 더 이상 방문할 노드가 없으면 이전 노드로 백트래킹
• 구현 : 재귀 또는 명시적인 스택 사용

---

💻 DFS 구현

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

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;  // 현재 노드 방문 처리
    cout << node << " ";  // 방문한 노드 출력

    for (int neighbor : graph[node]) {  // 현재 노드와 연결된 모든 이웃 노드 탐색
        if (!visited[neighbor]) {       // 방문하지 않은 노드라면 재귀 호출
            dfs(neighbor, visited, graph);
        }
    }
}

int main() {
    // 그래프 입력 (인접 리스트 방식)
    vector<vector<int>> graph = {
        {},        // 0번 노드 (사용하지 않음)
        {2, 3},    // 1번 노드와 연결된 노드들
        {1, 4, 5}, // 2번 노드와 연결된 노드들
        {1},       // 3번 노드와 연결된 노드들
        {2},       // 4번 노드와 연결된 노드들
        {2}        // 5번 노드와 연결된 노드들
    };
    vector<bool> visited(6, false);  // 방문 여부 배열

    cout << "DFS Traversal: ";
    dfs(1, visited, graph);  // 1번 노드부터 탐색 시작
    return 0;
}

---

💻 트리의 순회 방법

1. 전위 순회(Preorder Traversal)
   • 현재 노드 > 왼쪽 서브트리 > 오른쪽 서브트리

void preorder(Treenode* node, vector<int>& res) {
    if(!node)
    {
        return;
    }
    res.push_back(node->val); // 현재 노드 처리(순서를 출력할 res)
    preorder(node->left, res); // 왼쪽 서브트리 탐색
    preorder(node->right, res); // 오른쪽 서브트리 탐색
}

1. 중위 순회(Inorder Traversal)
   • 왼쪽 서브트리 > 현재 노드 > 오른쪽 서브트리

void inorder(TreeNode* node, vector<int>& res) {
    if(!node)
    {
        return;
    }
    inorder(node->left, res);
    res.push_back(node->val);
    inorder(node->right, res);
}

1. 후위 순회(Postorder Traversal)
   • 왼쪽 서브트리 > 오른쪽 서브트리 > 현재 노드

void postorder(Treenode* node, vector<int>& res) {
    if(!node)
    {
        return;
    }
    postorder(node->left, res);
    postorder(node->right, res);
    res.push_back(node->val);
}

---

📚 BFS

• 너비 우선 탐색
• 시간 복잡도 : (O(V+E))
• 공간 복잡도 : (O(V))
• 한 노드의 모든 인접한 노드를 먼저 방문한 뒤, 그 다음 단계로 넘어간다.
• 구현 방법은 큐 를 사용한다.

---

🔎 BFS 특징

• 탐색 방식 : 현재 레벨의 모든 노드를 방문한 후, 다음 레벨의 노드로 넘어감
• 구현 : 명시적인 큐(queue) 사용

---

💻 BFS 구현

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

void bfs(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false); // 방문 여부 배열
    queue<int> q;  // 탐색을 위한 큐

    q.push(start);  // 시작 노드를 큐에 추가
    visited[start] = true;  // 시작 노드 방문 처리

    while (!q.empty()) {
        int node = q.front();  // 큐의 첫 번째 노드를 가져옴
        q.pop();               // 큐에서 제거
        cout << node << " ";   // 방문한 노드 출력

        for (int neighbor : graph[node]) {  // 현재 노드의 모든 인접 노드 탐색
            if (!visited[neighbor]) {       // 방문하지 않은 노드라면
                q.push(neighbor);           // 큐에 추가
                visited[neighbor] = true;   // 방문 처리
            }
        }
    }
}

int main() {
    // 그래프 입력 (인접 리스트 방식)
    vector<vector<int>> graph = {
        {},        // 0번 노드 (사용하지 않음)
        {2, 3},    // 1번 노드와 연결된 노드들
        {1, 4, 5}, // 2번 노드와 연결된 노드들
        {1},       // 3번 노드와 연결된 노드들
        {2},       // 4번 노드와 연결된 노드들
        {2}        // 5번 노드와 연결된 노드들
    };

    cout << "BFS Traversal: ";
    bfs(1, graph);  // 1번 노드부터 탐색 시작
    return 0;
}

• c
• dfs
• bfs
• algorithm