탐색 - 너비우선탐색(Breath First Search), 깊이우선탐색(Depth First Search)

BFS (너비우선탐색)

BFS는 탐색을 할 때 너비를 우선으로 하는 알고리즘으로, '맹목적인 탐색'에 사용할 수 있는 탐색 기법이다. BFS에 사용되는 자료구조는 큐이다.

그럼 BFS의 알고리즘에 대해 알아보자.

 

1. 큐에서 하나의 노드를 꺼낸다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고 차례대로 큐에 삽입한다.

 

BFS는 위의 1번과 2번을 큐가 빌때까지 반복하면 된다.

이해를 위해 그림으로 나타내면 아래와 같다.

BFS

아래는 BFS의 간단한 코드이다.

 

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int number = 7;
int checked[7]; //방문기록
vector<int> a[8];
 
void bfs(int start) {
    queue<int> q;
    q.push(start);
    checked[start] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for (int i = 0; i < a[x].size(); i++) {
            int y = a[x][i];
            if (!checked[y]) {
                q.push(y);
                checked[y] = true;
            }
        }
    }
}
 
int main() {
    // 1 2 연결
    a[1].push_back(2);
    a[2].push_back(1);
    // 1 3 연결
    a[1].push_back(3);
    a[3].push_back(1);
    // 2 3 연결
    a[3].push_back(2);
    a[2].push_back(3);
    // 2 4 연결
    a[4].push_back(2);
    a[2].push_back(4);
    // 2 5 연결
    a[5].push_back(2);
    a[2].push_back(5);
    // 3 6 연결
    a[3].push_back(6);
    a[6].push_back(3);
    // 3 7 연결
    a[3].push_back(7);
    a[7].push_back(3);
    // 4 5 연결
    a[4].push_back(5);
    a[5].push_back(4);
    // 6 7 연결
    a[6].push_back(7);
    a[7].push_back(6);
 
    bfs(1);
    return 0;
}

 

위 코드를 실행하면 실행결과로 '1 2 3 4 5 6 7'이 나온다.

 

DFS (깊이우선탐색)

DFS는 맹목적으로 각 노드를 탐색할 때 사용되고, 큐를 사용하는 BFS와 다르게 스택이 사용된다. 추가적으로, 스택이 아닌 재귀로도 구현이 가능한데, 이는 재귀를 사용하는 것이 스택을 사용하는 것과 구조적으로 같기 때문이다. (컴퓨터는 구조적으로 항상 스택의 원리를 사용함)

그럼 DFS의 알고리즘에 대해 알아보자.

 

먼저, 시작 노드를 스택에 삽입 후 방문 처리한다.

1. 스택의 최상단 노드를 확인한다.

2. 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 이때, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

 

DFS는 더이상 방문할 노드가 없을 때까지(스택이 빌 때까지) 위의 1번과 2번을 반복하면 된다.

이해를 위해 그림으로 나타내면 다음과 같다.

DFS

아래는 DFS의 간단한 코드이다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int number = 7;
int checked[8]; //방문기록
vector<int> a[8];
 
void dfs(int x) {
    if (checked[x]) return;
    checked[x] = true;
    cout << x << ' ';
    for (int i = 0; i < a[x].size(); i++) {
        int y = a[x][i];
        dfs(y);
    }
}
 
int main() {
    // 1 2 연결
    a[1].push_back(2);
    a[2].push_back(1);
    // 1 3 연결
    a[1].push_back(3);
    a[3].push_back(1);
    // 2 3 연결
    a[3].push_back(2);
    a[2].push_back(3);
    // 2 4 연결
    a[4].push_back(2);
    a[2].push_back(4);
    // 2 5 연결
    a[5].push_back(2);
    a[2].push_back(5);
    // 3 6 연결
    a[3].push_back(6);
    a[6].push_back(3);
    // 3 7 연결
    a[3].push_back(7);
    a[7].push_back(3);
    // 4 5 연결
    a[4].push_back(5);
    a[5].push_back(4);
    // 6 7 연결
    a[6].push_back(7);
    a[7].push_back(6);
 
    dfs(1);
    return 0;
}

 

위 코드를 실행하면 실행 결과로 '1 2 3 6 7 4 5'가 나온다.

 

오늘은 BFS와 DFS에 대해 학습해보았다. 간단한 BFS와 DFS에 대해 잘 이해하고 있어야 이를 활용하는 문제를 더 쉽게 풀 수 있을 것이므로 BFS와 DFS에 대해 잘 기억하고 있어야겠다.