[알고리즘] DFS & BFS 🔗

안녕하세요.
오늘은 DFS와 BFS에 대해 알아보고, 이에 관련된 간단한 문제를 풀이해 볼까 합니다.

DFS & BFS

먼저 DFS와 BFS의 뜻에 대해 살펴보겠습니다.

DFS는 Depth-First Search, 깊이 우선 탐색이라는 의미를 갖고 있고, BFS는 Breadth-First Search, 너비 우선 탐색이라는 의미를 갖고 있습니다.

여기서 깊이와 너비라는 것을 알기 위해서는 무엇을 탐색하는지 알아야 하는데요,
주로 이 탐색 알고리즘은 그래프 혹은 트리를 탐색합니다.

여기서 그래프와 트리는 아래와 같은 차이점이 있습니다.

그럼 여기서 탐색 알고리즘의 깊이와 너비는 그래프나 트리의 깊이나 너비를 의미한다는 것을 알 수 있습니다.

DFS: 깊이 우선 탐색

최대한 깊게 내려간 뒤 대려갈 갈 곳이 없을 경우 옆으로 이동하는 알고리즘 입니다.

순서를 시각화 하면 위와 같은 순서대로 이동합니다.
그림을 보면 트리의 깊이 끝까지 내려갔다가 더이상 갈 깊이가 없을때 다음 분기로 넘어가는 모습을 볼 수 있습니다.

DFS는 상대적으로 BFS보다 구현이 간단하지만, 검색속도 자체는 BFS보다 느리다는 특징이 있습니다.

스택이나 제귀함수로 구현할 수 있습니다.

BFS: 너비 우선 탐색

최대한 넓게 이동한 다음, 더이상 갈 수 없을 때 아래로 이동하는 알고리즘 입니다.

시작하는 정점에서 인접한 곳 먼저 탐색하는 방법으로, 가장 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 순회하는 방법 입니다.

인접한 정점을 먼저 탐색하므로 최단 경로가 보장됩니다.

큐로 구현할 수 있습니다.

문제 풀이

DFS와 BFS

위 문제는 DFS와 BFS를 동시에 구현하는 문제인데요, 둘을 동시에 구현하기 좋은 문제입니다.

저는 DFS를 제귀로, BFS를 큐를 사용하여 문제를 해결하였습니다.

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

using namespace std;

vector<bool> dfsVisit(1001);
vector<bool> bfsVisit(1001);
vector<vector<int>> map(1001);

void dfs(int index) {
    cout << index << " ";
    for(int child: map[index]) {
        if (!dfsVisit[child]) {
            dfsVisit[child] = true;
            dfs(child);
        }
    }
}

int main() {
    int n, m, start;
    cin >> n >> m >> start;
    for (int i = 0; i < m; ++i) {
        int p, c;
        cin >> p >> c;
        map[p].push_back(c);
        map[c].push_back(p);
    }
    for (int i = 1; i < map.size(); i++) {
        sort(map[i].begin(), map[i].end());
    }
    dfsVisit[start] = true;
    dfs(start);
    cout << "\n";

    queue<int> Q;
    Q.push(start);
    bfsVisit[start] = true;
    while (!Q.empty()) {
        int select = Q.front();
        Q.pop();
        cout << select << " ";
        vector<int> input;
        for (int child: map[select]) {
            if (bfsVisit[child]) continue;
            bfsVisit[child] = true;
            Q.push(child);
        }
    }
}

마무리

오늘은 탐색 알고리즘 DFS와 BFS에 대해 설명해 드렸습니다.
처음 접하면 어려운 알고리즘 이지면 익숙해지면 어느 알고리즘보다 간단한 알고리즘 인것 같습니다..ㅋㅋ

읽어주셔서 감사합니다!