[알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)

너비 우선 탐색

너비 우선 탐색(Breadth First Search)은 넓게 탐색하는 알고리즘입니다.
너비 우선 탐색(이후 BFS)의 원리는 현재 노드의 자식 노드를 먼저 방문한다. 입니다.

미로를 예시로 설명 해보겠습니다.
저희는 어느 방에 있고 방에는 여러 개의 문이 있습니다.
원하는 방으로 이동하기 위해서 할 수 있는 행동은
현재 방에 있는 모든 문을 한 번씩 열어서 문 건너 방에 무엇이 있는지 확인할 수 있습니다.
확인한 건너편 방이 목적지가 아닐 경우, 문을 닫고 다른 문을 열어봐야합니다.
만약, 건너편 모든 방을 확인해도 원하는 방이 나오지 않았을 경우
문을 확인했던 순서로 건너편 방을 방문합니다.
건너편 방에서도 위의 과정을 반복합니다.

깊이 우선 탐색

깊이 우선 탐색(Depth First Search)은 깊게 탐색하는 알고리즘입니다.
깊이 우선 탐색(이후 DFS)의 원리는 자식 노드 발견시 바로 이동 입니다.

위의 BFS에서 설명에 사용했던 미로를 똑같이 사용해 설명해보겠습니다.
BFS에서는 모든 문을 열어보았지만, DFS에서는 문을 여는 행위가 곧 이동입니다.
즉, 현재 방에서 여러 문이 존재하지만 첫 번째 문을 열고 건너편 방으로 이동합니다.
그러나 이동만 하면 문이 없는 방에 도착하면 문제가 생길 수 있으므로
건너기 직전 방으로 돌아올 수 있도록 기록해야 합니다.

두 탐색의 차이

BFS는 반드시 모든 노드가 동일하고 간선에 가중치가 없을 때 라는 조건에서
최단거리, 이웃 탐색, 브로드캐스트 등의 문제에서 사용됩니다.

DFS는 노드 혹은 간선에 값 혹은 가중치가 존재하는 그래프에서
최단거리를 구할 때 주로 사용됩니다. 대표적으로 Dijkstra Algorithm 이 있습니다.
그 외에 최소 신장 트리 관련 문제와 그래프 사이클 탐색, 미로 탈출 등
여러 문제에서 DFS가 사용됩니다.

코드 구현

#include <iostream>
#include <queue>

std::queue<int> q;
bool *visited;
std::vector<int> *node;

void BFS(int start_node)
{
    q.push(start_node);
    visited[start_node] = true;

    while (!q.empty())
    {
        int current = q.front();
        q.pop();

        printf("%d ", current);

        // curr_node에 연결된 노드들을 차례로 방문
        for (int next : node[current])
        {
            if (!visited[next])
            {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

void DFS(int curr_node)
{
    visited[curr_node] = true;
    printf("%d ", curr_node);

    for (int next_node : node[curr_node])
    {
        if (false == visited[next_node])
        {
            DFS(next_node);
        }
    }
}

int main() 
{
	int node_cnt, edge_cnt, start_node;
    std::cin >> node_cnt >> edge_cnt >> start_node;

    visited = new bool[node_cnt + 1];
    node = new std::vector<int>[node_cnt + 1];

    std::fill(visited, visited + node_cnt + 1, false);
    for (int i = 0; i < edge_cnt; ++i)
    {
        int start, end;
        std::cin >> start >> end;
        node[start].push_back(end);
        node[end].push_back(start);
    }

    BFS(start_node);
    DFS(start_node);
}   
   

활용 문제

[BOJ]DFS와 BFS 구현하기