[알고리즘 공부] BFS & DFS (C++)

들어가기 전) 스택 & 큐

스택과 큐는 컴퓨터공학에서 가장 기본이 되는 자료구조.

#include <stack>
#include <queue>

로 C++ STL 라이브러리 사용 가능

stack은 s.top(), queue는 q.front() 로 가장 위/앞의 값을 가져올 수 있다.

---

 

BFS(Breadth First Searct, 너비 우선 탐색)

탐색할 때 너비를 우선으로 해서 탐색 수행하는 탐색 알고리즘
‘최단경로’를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용. 준비물은 큐(Queue)

맹목적인 탐색을 하고자 할 때 사용하는 탐색 기법.

맨 처음에는 시작 노드를 큐에 삽입하면서 시작. 시작 노드는 방문 처리 후, 다음의 간단한 알고리즘에 따라 작동.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드 방문하고, 차례대로 큐에 삽입

위 두 단계를 반복.

 

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

using namespace std;

int number = 7;
int c[7]; // 방문 check
vector<int> a[8]; // 노드 들어갈 vector. 1~7을 쓰기 위해 8로 설정했음.

void bfs(int start) {
    queue<int> q;
    q.push(start);
    c[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 (!c[y])
            {
                q.push(y);
                c[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[2].push_back(3);
    a[3].push_back(2);
    // 2-4
    a[2].push_back(4);
    a[4].push_back(2);
    // 2-5
    a[2].push_back(5);
    a[5].push_back(2);
    // 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;
}

 

- 거리가 가까운 노드들부터 탐색이 이루어짐.

- BFS는 너비를 우선으로 해서 탐색한다는 특성이 중요한 것이고, 다른 알고리즘에 적용하는 것이 핵심.
   그 자체로는 큰 의미가 없다고 볼 수 있음.

 

DFS(Depth First Search, 깊이 우선 탐색)

탐색할 때 깊이를 우선으로 해서 탐색 수행하는 탐색 알고리즘
스택이 사용됨. 근데 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에 따로 스택을 사용하지 않아도 구현이 가능함.

마찬가지로 맹목적으로 각 노드를 탐색할 때 주로 사용.

맨 처음에는 시작 노드를 스택에 삽입하면서 시작. 시작 노드는 방문 처리 후, 다음의 간단한 알고리즘에 따라 작동.

1. 스택의 최상단 노드를 확인
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺌.

위 두 단계를 반복.

 

#include <iostream>
#include <vector>

using namespace std;

int number = 7;
int c[8];
vector<int> a[8]; // 7개의 노드가 인접한 노드를 가질 수 있도록 함

void dfs(int x)
{
    // 방문했으면 끝내기
    if (c[x])
        return;
    c[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[2].push_back(3);
    a[3].push_back(2);
    // 2-4
    a[2].push_back(4);
    a[4].push_back(2);
    // 2-5
    a[2].push_back(5);
    a[5].push_back(2);
    // 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); // 1 2 3 6 7 4 5
    return 0;
}

기본적으로 재귀함수 자체가 컴퓨터의 내부적인 구조인 stack frame에 차곡차곡 쌓이는 형태 => 간단하게 재귀함수로 구현을 하는 것만으로도 스택에 담고 빼는 것과 같은 효과

• DFS도 그 자체로는 큰 의미가 없고 활용적인 목적으로 사용 가능