[BFS & DFS] DFS(Depth First Search)

이번에는 DFS, BFS에 대해서 공부해보겠습니다. 두 알고리즘은 graph를 탐색한는 알고리즘인데.. 먼저 의미하는게 무엇인지..!?

---

DFS Depth First Search 깊이 먼저 탐색

BFS Breadth First Search 너비 먼저 탐색

---

오호! 깊이와 너비의 차이가 있네요ㅎㅎ 이번 페이지에서는 DFS만 보고 다음 페이지에서 BFS를 해보겠습니다.ㅎㅎㅎ

DFS의 장단점은 어떤거가 있을까요???

DFS는 깊이있게 먼저 탐색하기 때문에 엄청 넓은 tree, graph에서 탐색에 용이하다는 점을 가지고 있습니다.

하지만! (뒤에서 나오겠지만) stack을 사용하기 때문에 너무 깊게 들어가다보면 overflow가 일어날 수 있다는 거죠.

보통 DFS는 Cycle Detection에 사용됩니다.

전 graph에서 DFS를 먼저 봤었는데, tree구조에서 먼저 보는게 도움이 많이 될 것 같아요. 그런 의미로! 간단한 tree 구조에서 탐색 방법을 살펴봅시다.

DFS

---

먼저 DFS입니다! 그림을 보니까 이해가 되시나요??? 깊이 먼저 탐색 이라는 말처럼 정말 자식 노드의 끝까지 찍고 나오는 모습을 볼 수 있네요. 한 우물씩 판다는 건가..ㅎㅎ graph에서는 vertex의 자식들을 탐색하면서 가게 되는데요. 하나하나 차근차근 봅시다.

그림을 보면 이해가되시나요?? 위에 tree처럼 역시 자식들을 먼저 탐색하는 식으로 가네요ㅎㅎ 그러면 구현은 어떻게 할까요??

먼저 필요한 것들을 생각해봅시다. 먼저 떠오르는게 뭘까요?? 코드나 주세요

자식을 탐색하는 동안 사용되지 않고 있는 자식을 저장할 저장소가 필요하겠죠?? 보통 stack을 사용합니다. 그림으로 한번 봅시다.

저는 dfs에서 자식 넣는 순서를 우선순위(번호)가 큰 순서대로 넣어서 작은 것 먼저 나오게 설계해보았습니다. 오해마시길..^^

이런 stack구조를 가지게 됩니다. 위에 graph이미지를 사용해서 설계한 것인데 이해가 되시나요??ㅎㅎ 그러리라 믿습니다..!!!

자 그럼 stack이 필요하다는 걸 알았고, 그 다음 필요한게 하나 더 있습니다. 지금 제가 간단하게 그린 graph에서도 vertex간에 이어진 부분이 많잖아요.

나중되면 양방향, 단방향 연결... 겁나 많이 연결 등등... 아주 복잡하게 되있는 graph가 많기 때문에 어떤 vertex를 방문했는지 체크를 해줘야합니다.

뭐 이부분이야 구조체 혹은 배열로 선언해주면 되기 때문에 쉽죠!! 그러면 한번 설계해봅시다..! 전 C++ STL stack를 사용하겠습니다. 왜냐면 귀찮으니까!!

만약 queue, stack에 대해 공부하겠다는 분들은 직접 설계해보시기를 추천합니다!!!

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

int main(){
    int map[7][7] = {
        {0,1,1,0,0,0,0},
        {1,0,0,1,0,1,0},
        {1,0,0,0,0,0,0},
        {0,1,0,0,1,0,1},
        {0,0,0,1,0,1,0},
        {0,1,0,0,1,0,0},
        {0,0,0,1,0,0,0}
    };
    bool visit[7] = {false};
    stack<int> s;
    s.push(0);
    visit[0] = true;
    while(!s.empty()){
        int temp = s.top();
        cout << temp + 1 << " -> ";
        s.pop();
        for(int i=6; i>=0; i--){
            if(map[temp][i] && !visit[i]){
                visit[i] = true;
                s.push(i);
            }
        }
    }
    cout << "end" << endl;
}

실행해보면 사진과 맞게 1 2 4 5 7 6 3 end 나오는걸 알 수 있습니다!!! 그럼 다음장에서 BFS를 공부해보겠습니다!!!! 빠이~!