[이론] DFS & BFS (+ 트리 순회)

 

깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)은 그래프 탐색에서 자주 사용되는 기본적인 알고리즘이다.

DFS는 한 노드의 끝까지 탐색한 후 돌아오는 방식이고, BFS는 가까운 노드부터 차례로 탐색해 나가는 방식이다.

오늘은 DFS와 BFS의 동작 원리와 구현 방법, 그리고 각각의 특징과 활용 사례를 알아보도록 하겠다.

 

---

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS) 시각화

 

DFS: 가능한 깊은 경로를 따라 탐색하다가 더 이상 깊이 갈 수 없을 때 뒤로 돌아가서 다른 경로를 찾는 방식

stack 혹은 재귀 함수를 통해 구현할 수 있다.

 

 

DFS 응용

• 탐색 경로: 미로 찾기 및 퍼즐 문제 등에서 특정 목표 지점에 도달하는 경로 탐색
• 백트래킹 문제: 조합, 순열 생성 등에서 백트래킹 기법과 함께 활용
• 사이클 탐지: 그래프에서 사이클이 존재하는지 검사
• 강한 연결 요소 찾기: 타잔(Tarjan) 알고리즘으로 강한 연결 요소를 찾을 수 있음

 

 

DFS 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[6];
int isVisited[6];

void dfs(int here) {
    cout << here << " 노드 방문\n";
    for (int there : graph[here]) {
        if (isVisited[there]) continue;
        isVisited[here] = 1;
        dfs(there);
    }
    cout << here << " 종료\n";
}

int main() {
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[4].push_back(2);
    
    dfs(1);
    
    return 0;
}

 

실행 결과

 

시간 복잡도: O (V + E)

방문 체크를 통해 무한 탐색에 빠지지 않도록 방문한 노드를 기록하는 것이 중요하다.

 

 

 

---

너비 우선 탐색(BFS)

너비 우선 탐색(BFS) 시각화

 

BFS: 가능한 깊은 경로를 따라 탐색하다가 더 이상 깊이 갈 수 없을 때 뒤로 돌아가서 다른 경로를 찾는 방식

queue을 활용하여 구현할 수 있다.

 

 

BFS 응용

• 최단 경로 찾기: 가중치가 없는 그래프에서 시작 - 목표까지의 최단 경로를 찾는데 적합
• 레벨별 노드 탐색: 특정 레벨에 따라 탐색 적합

 

 

BFS 코드

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

using namespace std;

vector<int> graph[6];
int isVisited[6];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    isVisited[start] = 1;
    
    while (q.size()) {
        int here = q.front();
        q.pop();
        cout << here << " 노드 방문\n";
        
        for (int there : graph[here]) {
            if (isVisited[there]) continue;
            isVisited[there] = 1;
            q.push(there);
        }
    }
}

int main() {
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[4].push_back(2);
    
    bfs(1);
    
    return 0;
}

 

실행 결과

 

시간 복잡도: O (V + E)

방문 체크를 통해 무한 탐색에 빠지지 않도록 방문한 노드를 기록하는 것이 중요하다.

 

 

 

---

DFS & BFS 비교

 

 

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 비교하면 아래와 같다.

 

탐색 방식	깊이 우선 탐색 (Deep into branches)	너비 우선 탐색 (Level-wise exploration)
자료 구조	스택 (Stack) - 보통 재귀 사용	큐 (Queue)
경로 특성	특정 경로 존재 여부 탐색에 적합	최단 경로 탐색에 적합 (가중치가 없는 그래프)
사용 사례	백트래킹, 미로 탐색, 순열/조합 문제	최단 경로 찾기, 연결성 탐색
메모리 사용	보통 더 적음	종종 더 많이 사용 (특히 노드가 많은 경우)
시간 복잡도	O(V + E)	O(V + E)
순서	깊이 우선으로 탐색	시작 노드에서 가까운 노드부터 순차적으로 탐색
노드 방문 순서	끝까지 탐색 후 백트래킹	인접한 모든 노드 먼저 탐색
경로 보장	최단 경로를 보장하지 않음	가중치가 없는 경우 최단 경로 보장
루프 방지 방법	방문 여부 배열 사용 또는 조건 설정	방문 여부 배열 사용
구현 방식	재귀 함수나 명시적 스택 사용	큐 자료구조 사용 (FIFO)
예시 문제	미로에서 특정 목표 찾기, 순열 생성	미로 최단 탈출 경로, 사회적 거리 측정 문제

 

 

 

---

트리 순회

트리 순회(Tree Traversal)는 트리 자료구조의 모든 노드를 특정한 순서대로 방문하는 방법을 의미한다.

트리 순회 종류는 크게 전위 순회, 중위 순회, 후위 순회, 레벨 순회 네 가지로 나뉜다.

각각의 순회 방법은 노드를 방문하는 순서가 다르기 때문에 목적에 따라 적합한 방식을 사용하면 된다.

 

 

1. 전위 순회 (Preorder Traversal)

void preorderTraversal(Node* node) {
    cout << node->key << " ";  // 현재 노드를 방문
    preorderTraversal(node->left);
    preorderTraversal(node->right);
}

 

 

 

2. 중위 순회 (Inorder Traversal)

void inorderTraversal(Node* node) {
    inorderTraversal(node->left);
    cout << node->key << " ";  // 현재 노드를 방문
    inorderTraversal(node->right);
}

 

 

3. 후위 순회 (Postorder Traversal)

void postorderTraversal(Node* node) {
    postorderTraversal(node->left);
    postorderTraversal(node->right);
    cout << node->key << " ";  // 현재 노드를 방문
}

 

 

---

정리

BFS와 DFS는 각각 너비 우선, 깊이 우선으로 그래프와 트리를 탐색하며, 서로 다른 탐색 경로와 목적에 따라 활용된다. 트리 순회는 전위, 중위, 후위, 레벨 순으로 노드를 방문하여 다양한 작업을 수행할 수 있도록 한다. 문제의 특성과 목표에 따라 적절한 탐색 방법과 순회를 선택하는 것이 중요하다. 코딩 테스트에서 한 문제는 등장하는 개념이므로 반드시 관련된 문제를 풀어보도록 하자.