[알고리즘] BFS, DFS (c++, js)

서론

 

BFS와 DFS는 코딩 테스트에 자주 등장하는 유형이다.

꼭 한 문제씩은 출제되는 경향이 있기 때문에 이번 알고리즘 스터디에서 BFS와 DFS 완벽 마스터를 목표로 여러 문제를 풀기로 했다.

문제를 풀기 이전에, 개념을 명확하게 이해하고 넘어가고자 포스팅하게 되었다.

 

 

---

BFS, DFS란?

BFS와 DFS는 모두 그래프를 탐색하는 알고리즘이다.

*여기서 그래프는 정점과 간선을 가진 자료구조이다.

 

이중에서 너비를 우선하냐, 깊이를 우선하냐에 따라 두 가지 방법으로 나뉜다.

1. BFS: Breadth First Search - 너비 우선 탐색
2. DFS: Depth First Search - 깊이 우선 탐색

 

그렇다면 너비, 깊이를 우선한다는게 무슨 말일까?

 

BFS는 너비를 우선한다.

가까운 것 부터 넓게 탐색하는 것이 핵심이다.

마치 호수에 돌을 던졌을 때 물결이 동심원을 그리며 퍼져나가는 모습과 유사하다.

 

DFS는 깊이를 우선한다.

하나의 경로를 끝까지 탐색하는 것이 핵심이다.

마치 미로를 찾을 때 한쪽 벽을 계속 따라가는 것과 유사하다.

 

그래프

위와 같은 그림의 그래프가 있을 때 각각 BFS, DFS의 방문 경로를 보면 어느정도 이해할 수 있다.

 

BFS: 2 -> 3 -> 4 -> 5를 방문하게 된다.

DFS: 2 -> 4 -> 3 -> 5를 방문하게 된다.

---

BFS

개념

1. 너비 우선: 가까운 정점부터 차례대로 방문한다.
2. 같은 레벨 우선: 루트에서 출발하여 같은 레벨(깊이)에 있는 모든 노드를 먼저 방문한다.

구현

1. 큐로 구현

2. 재귀로 구현

 

(1) 큐로 구현

BFS는 먼저 들어온 것을 먼저 처리하는 선입선출(FIFO) 방식으로 동작해야 하므로, 자료구조 큐(Queue)를 사용하여 구현한다.

동작 과정:

1. 탐색 시작 정점을 큐에 넣고 방문 처리를 한다.
2. 큐가 빌 때까지 다음을 반복한다.
   • a. 큐에서 정점을 하나 꺼낸다.
   • b. 해당 정점과 인접한 정점 중 아직 방문하지 않은 정점들을 모두 큐에 넣고 방문 처리를 한다.

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

using namespace std;

// 그래프를 인접 리스트로 표현
vector<int> adj[9];
bool visited[9] = {false,};

// 큐를 이용한 BFS 함수
void bfs_queue(int startNode) {
    queue<int> q;

    // 시작 노드를 큐에 삽입하고 방문 처리
    q.push(startNode);
    visited[startNode] = true;
    cout << startNode << " ";

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int currentNode = q.front();
        q.pop();

        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < adj[currentNode].size(); ++i) {
            int nextNode = adj[currentNode][i];
            if (!visited[nextNode]) {
                q.push(nextNode);
                visited[nextNode] = true;
                cout << nextNode << " ";
            }
        }
    }
}

int main() {
    // 그래프 연결 관계 설정 (1번 노드부터 시작)
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[1].push_back(8);

    adj[2].push_back(1);
    adj[2].push_back(7);

    adj[3].push_back(1);
    adj[3].push_back(4);
    adj[3].push_back(5);

    adj[4].push_back(3);
    adj[4].push_back(5);

    adj[5].push_back(3);
    adj[5].push_back(4);

    adj[6].push_back(7);

    adj[7].push_back(2);
    adj[7].push_back(6);
    adj[7].push_back(8);

    adj[8].push_back(1);
    adj[8].push_back(7);

    cout << "BFS (Queue) 방문 순서: ";
    bfs_queue(1);
    cout << endl;

    return 0;
}

BFS (Queue) 방문 순서: 1 2 3 8 7 4 5 6

 

(2) 재귀로 구현

재귀를 이용한 BFS는 일반적이지 않지만, 구현은 가능하다.

이 방식은 다음 레벨의 모든 노드를 큐에 담아 재귀 함수의 인자로 넘기는 형태로 동작한다.

깊이 우선 탐색(DFS)의 재귀 구현과는 달리, 한 번의 재귀 호출이 한 레벨의 탐색을 담당한다.

동작 과정:

1. 현재 레벨의 정점들이 담긴 큐를 인자로 받는 재귀 함수를 정의한다.
2. 재귀 함수는 큐가 비어있으면 종료한다.
3. 다음 레벨에 방문할 정점들을 담을 새로운 큐(next_q)를 생성한다.
4. 현재 레벨의 큐가 빌 때까지 반복한다.
   • a. 큐에서 정점을 꺼내 방문하고, 아직 방문하지 않은 이웃 정점들을 next_q에 추가하고 방문 처리합니다.
5. next_q를 인자로 하여 재귀 함수를 다시 호출합니다.

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

using namespace std;

// 그래프를 인접 리스트로 표현
vector<int> adj_rec[9];
bool visited_rec[9] = {false,};

// 재귀를 이용한 BFS 함수
void bfs_recursive(queue<int>& q) {
    // 현재 큐가 비어있으면 재귀 종료 (기저 사례)
    if (q.empty()) {
        return;
    }

    // 다음 레벨의 노드를 저장할 큐
    queue<int> next_q;
    
    // 현재 레벨의 모든 노드를 처리
    while (!q.empty()) {
        int currentNode = q.front();
        q.pop();

        // 현재 노드와 연결된, 아직 방문하지 않은 노드들을 다음 큐에 추가
        for (int neighbor : adj_rec[currentNode]) {
            if (!visited_rec[neighbor]) {
                visited_rec[neighbor] = true;
                cout << neighbor << " ";
                next_q.push(neighbor);
            }
        }
    }

    // 다음 레벨의 노드들로 재귀 호출
    bfs_recursive(next_q);
}

int main() {
    // 그래프 연결 관계 설정 (1번 노드부터 시작)
    adj_rec[1].push_back(2);
    adj_rec[1].push_back(3);
    adj_rec[1].push_back(8);
    // ... (큐 방식 예제와 동일한 그래프)
    adj_rec[2].push_back(1); adj_rec[2].push_back(7);
    adj_rec[3].push_back(1); adj_rec[3].push_back(4); adj_rec[3].push_back(5);
    adj_rec[4].push_back(3); adj_rec[4].push_back(5);
    adj_rec[5].push_back(3); adj_rec[5].push_back(4);
    adj_rec[6].push_back(7);
    adj_rec[7].push_back(2); adj_rec[7].push_back(6); adj_rec[7].push_back(8);
    adj_rec[8].push_back(1); adj_rec[8].push_back(7);


    cout << "BFS (Recursive) 방문 순서: ";
    
    // 시작 준비
    queue<int> start_q;
    int startNode = 1;

    start_q.push(startNode);
    visited_rec[startNode] = true;
    cout << startNode << " ";

    // 재귀 함수 호출
    bfs_recursive(start_q);
    cout << endl;

    return 0;
}

BFS (Recursive) 방문 순서: 1 2 3 8 7 4 5 6

---

DFS

개념

1. 깊이 우선: 가까운 것 부터 차례대로 방문한다.
2. 같은 레벨 우선: 루트에서 출발하여 같은 레벨(깊이)에 있는 모든 노드를 먼저 방문한다.

구현

(1) 재귀로 구현

동작 과정:

1. 탐색 시작 정점을 방문 처리하고, 바로 출력한다.
2. 해당 정점과 인접한 정점들을 순회한다.
3. 아직 방문하지 않은 인접 정점이 있다면, 그 정점을 시작으로 재귀 함수를 즉시 호출한다.
4. 모든 인접 정점을 확인했으면 (더 갈 곳이 없으면) 함수가 종료되고, 직전 호출(갈림길)로 돌아간다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// BFS 예제와 동일한 그래프
vector<int> adj_dfs[9];
bool visited_dfs[9] = {false,};

void dfs_recursive(int currentNode) {
    // 현재 노드 방문 처리
    visited_dfs[currentNode] = true;
    cout << currentNode << " ";

    // 인접 노드 탐색
    for (int i = 0; i < adj_dfs[currentNode].size(); ++i) {
        int nextNode = adj_dfs[currentNode][i];
        // 3. 방문하지 않은 노드라면 즉시 재귀 호출
        if (!visited_dfs[nextNode]) {
            dfs_recursive(nextNode);
        }
    }
    // (더 갈 곳이 없으면 함수 자동 종료 -> 백트래킹)
}

int main() {
    // 그래프 연결 관계 설정 (BFS 예제와 동일)
    adj_dfs[1].push_back(2);
    adj_dfs[1].push_back(3);
    adj_dfs[1].push_back(8);
    // ... (나머지 그래프 연결)
    adj_dfs[2].push_back(1); adj_dfs[2].push_back(7);
    adj_dfs[3].push_back(1); adj_dfs[3].push_back(4); adj_dfs[3].push_back(5);
    adj_dfs[4].push_back(3); adj_dfs[4].push_back(5);
    adj_dfs[5].push_back(3); adj_dfs[5].push_back(4);
    adj_dfs[6].push_back(7);
    adj_dfs[7].push_back(2); adj_dfs[7].push_back(6); adj_dfs[7].push_back(8);
    adj_dfs[8].push_back(1); adj_dfs[8].push_back(7);

    cout << "DFS (Recursive) 방문 순서: ";
    dfs_recursive(1); // 1 2 7 6 8 3 4 5
    cout << endl;

    return 0;
}

---

비교

그렇다면 어떤 문제 풀이 상황에 어떤 방법을 써야 할까?

보통 모든 경우를 탐색해야 한다면 BFS가 더 유용하다.

 

모두 요약해서 아래 표로 정리해보았다.

 

항목	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	너비 우선 (Level-by-Level)	깊이 우선 (Path-by-Path)
핵심 원리	물결 (가까운 노드부터 탐색)	한길 파기 (끝까지 갔다가 복귀)
자료구조	큐 (Queue) - FIFO	스택 (Stack) - LIFO (또는 재귀)
주요 사용처	최단 거리, 최소 비용 보장	경로 존재 여부, 백트래킹, 연결 요소
속도 (N:노드, E:간선)	$O(N+E)$	$O(N+E)$
특징	경로가 너무 깊으면 유리 메모리 소모 큼 (큐에 모든 자식을 담음)	최단 거리 보장 X 메모리 소모 적음 (한 경로만 기억)