[알고리즘] DFS와 BFS

개념

BFS와 DFS는 그래프(또는 트리)에서 노드를 탐색하는 두 가지 주요 알고리즘입니다.

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

BFS는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 가장 가까운 노드부터 탐색하며 너비 방향으로 탐색합니다. 다음과 같은 방식으로 동작합니다:

1. 시작 노드를 선택하고, 해당 노드와 인접한 모든 노드를 큐(Queue)에 넣습니다.

2. 큐에서 노드를 하나씩 꺼내며 방문하고, 해당 노드와 인접한 노드들을 큐에 추가합니다.

3. 큐가 빌 때까지 반복합니다.

BFS의 장점:

1. 최단 경로 탐색에 유용합니다. 루트 노드에서부터 가까운 노드부터 방문하기 때문에 최단 경로를 찾을 수 있습니다.
2. 모든 레벨(깊이)의 노드를 탐색하므로, 깊은 레벨에 있는 노드를 먼저 발견할 수 있습니다.
3. 큐를 사용하기 때문에, 재귀 함수를 사용하지 않고 반복적인 구현이 가능합니다.

BFS의 단점:

1. 메모리 사용량이 많을 수 있습니다. 너비 방향으로 레벨별로 노드를 저장해야 하므로, 그래프가 크면 메모리 부하가 커질 수 있습니다.
2. 그래프의 깊이가 깊을 경우, BFS는 비효율적일 수 있습니다.

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

DFS는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 깊이 방향으로 탐색합니다. 다음과 같은 방식으로 동작합니다:

1. 시작 노드를 선택하고, 해당 노드의 자식 노드 중 하나를 선택해 재귀적으로 탐색합니다.
2. 더 이상 자식 노드가 없을 때까지 진행하고, 더 이상 진행할 수 없을 때 이전 노드로 돌아가서 다른 자식 노드를 선택합니다.
3. 모든 노드를 방문할 때까지 이 과정을 반복합니다.

DFS의 장점:

1. 메모리 사용량이 상대적으로 적습니다. 깊이 우선 탐색은 스택(Stack) 또는 재귀를 사용하므로 메모리 사용량이 크게 증가하지 않습니다.
2. 그래프의 깊이가 깊은 경우에 유용합니다. 가장 깊은 노드로 빠르게 이동할 수 있습니다.

DFS의 단점:

1. 최단 경로를 찾는 데 적합하지 않습니다. 먼저 발견한 경로가 최단 경로가 아닐 수 있습니다.
2. 무한 루프에 빠질 수 있습니다. 사이클이 있는 경우, 무한 루프에 빠질 가능성이 있습니다.

따라서, BFS는 최단 경로 찾기와 너비 기준 탐색에 유용하며, DFS는 깊이 기준 탐색 및 특정 문제에 적합한 경우가 있습니다. 탐색 문제에 따라 어떤 알고리즘이 적절한지 선택해야 합니다.

관련 코딩테스트 문제

리코쳇 로봇

무인도탐험

예제 코드 (C++)

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

class Graph {
public:
    int V; // 노드의 개수
    vector<vector<int>> adj; // 인접 리스트

    Graph(int vertices) : V(vertices), adj(vertices) {}

    // 무방향 그래프에 간선 추가
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // BFS 구현
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;

        visited[start] = true;
        q.push(start);

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

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }

    // DFS 구현 (재귀)
    void DFS(int node, vector<bool>& visited) {
        visited[node] = true;
        cout << node << " ";

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                DFS(neighbor, visited);
            }
        }
    }

    void DFS(int start) {
        vector<bool> visited(V, false);
        DFS(start, visited);
        cout << endl;
    }
};

int main() {
    Graph graph(6);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(3, 5);

    cout << "BFS (시작 노드 0): ";
    graph.BFS(0);

    cout << "DFS (시작 노드 0): ";
    graph.DFS(0);

    return 0;
}