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

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

 

그래프란 노드(Node)과 간선(Edge)로 이루어진 자료구조로, 그래프를 탐색한다는 것은 모든 정점을 방문하는 과정을 의미한다. DFS와 BFS는 이러한 정점을 방문하는 과정에서의 차이로 구분된다.

 

이 글에서는 DFS와 BFS에 대해 이야기 해볼것이다.

깊이 우선 탐색 (DFS)

이름에서 알 수 있는 DFS는 깊이를 우선한다. 즉, 분기를 만나면 현재 진행 중인 분기를 완전히 깊게 탐색을 마친 후 다음 분기를 탐색한다.

DFS는 다음과 같은 특징을 갖는다.

1. 모든 노드를 방문할 때 주로 사용한다.
2. 구현이 BFS보다 간단하다.
3. 검색속도 자체는 BFS보다 느리다.

a. 구현

(1) 인접 행렬을 이용한 구현

#include <iostream>

using namespace std;

int n, s, a[50][50], visited[50]={};

void DFS(int cur) {
    visited[cur]=1;
    cout << cur << " ";
    for(int i=0; i<n; i++)
        if(a[cur][i] && !visited[i]) DFS(i);
}

int main() {
    cin >> n >> s;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) cin >> a[i][j];
    DFS(s);
}

(2) 인접리스트를 이용한 구현

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

using namespace std;

vector<int> a[50];
int visited[50] = {};

void DFS(int cur) {
    visited[cur] = 1;
    cout << cur << " ";
    for (int i = 0; i < a[cur].size(); i++) {
        int next = a[cur][i];
        if (!visited[next]) DFS(next);
    }
}

int main() {
    int n, e;
    cin >> n >> e;
    for (int i = 0; i < e; i++) {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i = 0; i < n; i++) sort(a[i].begin(), a[i].end());
}

b. 장단점

(1) 장점 ✅

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
• 찾으려는 노드가 깊이 있는 경우 BFS 보다 빠르게 찾을 수 있다.

(2) 단점 🚨

• 해가 없는 경로를 탐색할 경우에도 끝까지 탐색한다.
• 얻어진 해가 최단 경로라는 보장이 없다. (해에 도달시 탐색을 종료하므로)

c. PS 할때는?

• 주로 끝까지 갈떄 사용한다.
• 영역 구분 문제에서 쓴다.
• 경로의 특징을 저장해야하는 문제에서 쓴다. (ex : 같은 숫자가 적힌 도로는 지나가면 안된다)
• 검색 대상 그래프가 클 때 쓴다.

---

깊이 우선 탐색 (BFS)

여기서도 이름에서 알 수 있듯 BFS는 너비를 우선한다. 즉, 분기를 만나면 계속 옆 애들을 둘러보면서 내려온다.

BFS는 다음과 같은 특징을 갖는다.

1. 주로 두 노드 사이의 최단 경로를 구할 때 사용한다.
2. Queue(또는 Deque)를 이용하여 구현한다.
3. 검색 속도 자체는 DFS보다 느리다.

a. 구현

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

using namespace std;

vector<int> a[50];
int n, e, s, visited[50]={};

void BFS() {
    queue<int> q;
    q.push(s);
    visited[s]=1;
    while(!q.empty()) {
        int cur = q.front();
        cout << cur << " ";
        q.pop();
        for(int i=0; i<a[cur].size(); i++) {
            int now = a[cur][i];
            if(!visited[now]){
                q.push(now);
                visited[now]=1;   
            }
        }
    }
}

int main() {
    cin >> n >> e >> s;
    for(int i=0; i<e; i++){
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i=0; i<n; i++) sort(a[i].begin(), a[i].end());
    BFS();
}

b. 장단점

(1) 장점 ✅

• 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한하다고 해도 답을 찾을 수 있다.

(2) 단점 🚨

• 경로가 매우 긴 경우에는 탐색 가지가 급격히 증가하며 많은 메모리를 요한다.
• 해가 존재하지 않는다면 모든 그래프를 탐색후 실패로 끝난다.
• 무한 그래프에서는 해를 찾지 못하고 끝나지도 않는다.

c. PS 할때는?

• 최단 경로 거리 문제를 풀때 쓴다.
• 검색 대상 그래프가 작을 때 사용한다.