[Algorithm] DFS와 BFS

그래프 탐색

그래프 탐색은 그래프(Graph)라는 자료 구조에서 특정한 목적을 가지고 노드(Node)나 정점(Vertex)을 탐색하거나 찾는 작업을 의미합니다. 그래프는 여러 개의 노드와 이를 연결하는 간선(Edge)으로 구성되며, 다양한 형태의 데이터나 객체 간의 관계를 모델링할 때 사용된다. 그중 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 대표적이다.

 

 

깊이 우선 탐색(DFS)

---

깊이 우선 탐색(DFS)은 그래프의 모든 노드를 방문하고자 할 때 사용되는 알고리즘 중 하나다. DFS는 스택(stack) 자료구조를 사용하여 구현하며, 더 이상 진행할 수 없을 때까지 한 경로를 탐색한 후, 다른 경로로 이동하여 탐색을 계속한다.

 

 

동작원리

1. 시작 노드를 스택에 넣고 방문 표시를 합니다.
2. 스택이 빌 때까지 다음 동작을 반복한다.
   • 스택에서 노드를 하나 꺼낸다.
   • 꺼낸 노드의 인접 노드 중에서 방문하지 않은 노드를 스택에 넣고 방문 표시한다.
3. 스택이 비면 모든 노드를 방문한 것이다.

코드

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

// 그래프의 인접 리스트를 표현하는 구조체
struct Graph 
{
    int V; // 노드의 수
    vector<vector<int>> adj; // 인접 리스트

    Graph(int V) : V(V)
    {
        adj.resize(V);
    }

    // 간선을 추가하는 함수
    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
    }
};


// 가독성을 위해 재귀함수로 구현하였다.
// 재귀 함수를 이용한 DFS 구현
void DFS(const Graph& G, int current, vector<bool>& visited) 
{
    visited[current] = true;
    cout << current << " ";

    for (int neighbor : G.adj[current]) //현재 노드에서 갈 수 있는 모든 이웃만큼 반복
    {
        if (!visited[neighbor]) //방문하지 않은 노드인지 확인한다.
        {
            DFS(G, neighbor, visited); //방문한적이 없다면 재귀적으로 함수를 호출하여서 현재 노드에서 이웃 노드로 이동한다. 
        }
    }
}

int main() 
{
    int v, inputX, inputY;
    cout << "간선의 갯수 : ";
    cin >> v;
    Graph G(v);

    for(int i= 0; i < v; i++)
    {
        cin >> inputX >> inputY;
        G.addEdge(inputX, inputY);
    }

    vector<bool> visited(v, false);

    cout << "DFS: ";
    DFS(G, 0, visited);
    cout << endl;

    return 0;
}

장점	단점
간단하고 직관적임	최단 경로를 찾는 문제에 적합하지 않음
깊이에 따라 탐색하기 때문에 깊은 경로를 먼저 탐색함	무한 루프에 빠질 가능성이 있음

 

너비 우선 탐색(BFS)

---

너비 우선 탐색(BFS)은 그래프의 모든 노드를 너비 방향으로 탐색하는 알고리즘이다. BFS는 큐(queue) 자료구조를 사용하여 구현하며, 시작 노드로부터 가까운 노드부터 방문한다.

 

동작원리

1. 시작 노드를 큐에 넣고 방문 표시를 한다.
2. 큐가 빌 때까지 다음 동작을 반복한다.
   • 큐에서 노드를 하나 꺼낸다.
   • 꺼낸 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 넣고 방문 표시를 한다.
3. 큐가 비면 모든 노드를 방문한 것이다.

코드

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

// 그래프의 인접 리스트를 표현하는 구조체
struct Graph 
{
    int V; // 노드의 수
    vector<vector<int>> adj; // 인접 리스트

    Graph(int V) : V(V)
    {
        adj.resize(V);
    }

    // 간선을 추가하는 함수
    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
    }
};

void BFS(const Graph& G, int start) 
{
    vector<bool> visited(G.V, false);
    queue<int> queue; // BFS를 위한 큐를 생성한다. 큐를 사용하여 방문할 노드를 유지하고, 먼저 들어온 노드부터 방문한다.

    queue.push(start); // 시작 노드를 큐에 추가하고 방문 표시를 합니다.
    visited[start] = true;

    while (!queue.empty()) //큐가 비어있지 않은 동안 다음 동작을 반복한다.
    {
        int current = queue.front(); //큐의 맨 앞에 있는 노드를 꺼내고 current에 저장한다.
        queue.pop();                // 꺼낸 노드를 큐에서 제거한다.
        cout << current << " ";     // 현재 노드를 출력하여 방문 순서를 표시한다.

        for (int neighbor : G.adj[current]) //현재 노드의 인접 노드를 순회하면서 방문되지 않은 이웃 노드를 큐에 추가하고 방문 표시를 한다. 이로써 다음 레벨의 노드로 한다.
        {
            if (!visited[neighbor]) 
            {
                queue.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}


int main() 
{
    int v, inputX, inputY;
    cout << "간선의 갯수 : ";
    cin >> v;
    Graph G(v);

    for(int i= 0; i < v; i++)
    {
        cin >> inputX >> inputY;
        G.addEdge(inputX, inputY);
    }

    vector<bool> visited(v, false);

    cout << "BFS: ";
    BFS(G, 0);
    cout << endl;

    return 0;
}

장점	단점
최단 경로를 찾는데 적합	깊은 경로를 먼저 탐색하는 DFS와 달리, 먼 노드를 먼저 탐색하므로 메모리를 많이 사용함
무한 루프에 빠질 가능성이 적음

 

결론

---

DFS와 BFS는 그래프 탐색 알고리즘 중에서 매우 유용한 도구로, 다양한 문제 해결에 적용할 수 있다. 두 알고리즘을 잘 이해하고 활용한다면 다양한 그래프 기반 문제를 효과적으로 해결할 수 있을 것이다.