[알고리즘] 그래프 탐색: DFS, BFS

그래프 탐색 알고리즘 중 가장 기본이 되는 DFS(깊이 우선 탐색)과 BFS(넓이 우선 탐색)에 대해 알아보겠습니다. 트리 구조에서 탐색이 어떻게 이루어지는 지를 통해 소개하겠습니다. 

동작 설명을 위해 트리 구조에서 하는 것일 뿐 그래프 종류와 관련없이 사용 가능합니다.

트리 구조

---

DFS(깊이 우선 탐색)이란?

DFS는 그래프의 한 노드에서 시작해 가능한 깊이까지 탐색을 진행한 뒤, 더 이상 갈 수 없을 때 다음 경로를 탐색하는 방식입니다. 재귀나 스택을 사용하여 구현할 수 있으며, 후입선출(LIFO) 구조를 따릅니다.

DFS 예시

DFS의 동작 방식

1. 시작 노드를 방문하고, 방문 처리를 합니다.
2. 방문하지 않은 인접 노드가 있다면 그 노드로 이동합니다.
3. 더 이상 방문할 노드가 없으면 이전 노드로 돌아갑니다.

DFS 탐색 순서

 

DFS를 통해 트리를 구성한다면 다음과 같습니다.

노드가 확장되는 순서

예시 코드(재귀)

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

bool visit[6];
vector<vector<int>> graph(6);

void dfs(int x) {
    // 현재 노드를 방문 처리
    visit[x] = true;
    cout << x << " ";

    // 인접 노드 탐색
    for (int y : graph[x]) {
        if (!visit[y]) {
            dfs(y);
        }
    }
}

int main() {
    // 그래프 생성
    graph[0] = { 1, 2 };
    graph[1] = { 0, 3, 4 };
    graph[2] = { 0, 5 };
    graph[3] = { 1 };
    graph[4] = { 1 };
    graph[5] = { 2 };

    cout << "DFS 탐색 순서: ";
    dfs(0); // 0번 노드에서 시작
    return 0;
}

결과

 

 

---

BFS(너비 우선 탐색)이란?

BFS는 그래프의 한 노드에서 시작해 인접한 모든 노드를 탐색한 후, 그 다음 깊이로 이동하는 방식입니다.
큐를 사용하여 구현하며, 선입선출(FIFO) 구조를 따릅니다.

 

BFS의 동작 방식

1. 시작 노드를 큐에 넣고 방문 처리를 합니다.
2. 큐에서 노드를 꺼내 인접 노드를 탐색합니다.
3. 방문하지 않은 노드는 큐에 삽입하고 방문 처리합니다.

BFS 탐색 순서

아래는 BFS의 노드 확장 순서입니다.

노드 확장 순서

예시 코드

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

vector<vector<int>> graph(6);
bool visit[6];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visit[start] = true;

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

        for (int y : graph[x]) {
            if (!visit[y]) {
                q.push(y);
                visit[y] = true;
            }
        }
    }
}

int main() {
    // 그래프 생성
    graph[0] = { 1, 2 };
    graph[1] = { 0, 3, 4 };
    graph[2] = { 0, 5 };
    graph[3] = { 1 };
    graph[4] = { 1 };
    graph[5] = { 2 };

    cout << "BFS 탐색 순서: ";
    bfs(0); // 0번 노드에서 시작
    return 0;
}

결과

 

---

DFS vs BFS

탐색 방식	깊이를 우선으로 탐색	너비를 우선으로 탐색
구현 방법	재귀, 스택 사용	큐 사용
시간 복잡도	O(V + E)	O(V + E)
특징	경로를 탐색하는 문제에 적합	최단 거리를 구하는 문제에 적합

 

DFS는 일반적으로 재귀로 구현하는데 재귀는 콜 스택을 사용하기 때문입니다. BFS를 큐로 구현하는 것처럼 DFS를 스택에 넣고 q.front()를 s.top()으로 사용하면 동일하게 구현할 수 있습니다. 즉, DFS와 BFS는 사용하는 자료구조만 다를 뿐 구현은 동일합니다.

 

---

정리

DFS와 BFS는 그래프 탐색의 가장 기본적인 알고리즘입니다.
각 알고리즘의 특징과 차이를 이해하고 문제 상황에 맞게 선택하는 것이 중요합니다.

 

추천 문제

https://www.acmicpc.net/problem/2606

https://www.acmicpc.net/problem/1260

https://www.acmicpc.net/problem/2178

https://www.acmicpc.net/problem/7576

https://www.acmicpc.net/problem/2206