BFS, DFS

먼저 완전 탐색의 방법에는

 

1. brute force

 

2. 비트마스크

 

3. 순열

 

4. 백트래킹

 

5. bfs, dfs

 

가 있다.

 

완전탐색을 공부하기 위해 brute force 문제를 계속해서 풀다가 이제는 bfs, dfs 문제를 풀어봐야겠다는 생각에 글을 적게 됐다.

 

먼저, 기본 개념은 https://www.youtube.com/watch?v=_hxFgg7TLZQ

이 영상이 굉장히 큰 도움이 됐다.

---

DFS(깊이 우선 탐색(최대한 깊게 파고 들어간다.))를 위해서는 stack이 필요하다. stack에 한번 담았던 node들은 다시 담지 않는다.

 

1. stack을 만든다.

 

2. 시작 node를 stack에 넣는다.

 

3. stack에서 1개를 꺼낸다.

 

4. 꺼낸 node의 child들을 stack에 담는다.

 

5. 3번에서 꺼낸 node는 출력한다.

 

6. 3~5번을 계속해서 반복한다.

 

기본 코드는 다음과 같다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int number=7;
bool c[7];
vector<int> a[8];

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()
{
    a[1].push_back(2);
    a[2].push_back(1);

    a[1].push_back(3);
    a[3].push_back(1);

    a[1].push_back(4);
    a[4].push_back(1);

    a[2].push_back(4);
    a[4].push_back(2);

    a[2].push_back(5);
    a[5].push_back(2);

    a[3].push_back(6);
    a[6].push_back(3);
    
    a[3].push_back(7);
    a[7].push_back(3);

    a[4].push_back(5);
    a[5].push_back(4);

    a[6].push_back(7);
    a[7].push_back(6);

    dfs(1);
}

dfs의 시작에서는 반드시 기저 사례를 정의해주어야 한다. dfs는 stack을 통해 직접 구현할 수도 있지만 보통 system stack(recursion)을 많이 활용하기 때문이다. recursion에서 탈출하는 기저 사례의 작성은 필수적이다.

 

---

BFS(너비 우선 탐색)의 경우에는 dfs의 과정과 거의 완전히 동일하다. 다른점 딱 하나는 dfs는 stack을 활용한다는 것, bfs는 queue를 활용한다는 점에서 차이를 가진다.

 

기본 코드는 다음과 같다.

 

/***************
          1
        /   \
      2 ------3
     / \     / \    
    4---5   6---7

    이런 모양의 이진 트리가 있다고 가정했을 때의 bfs  
****************/

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

using namespace std;

int number=4;
bool c[4]; //방문했는지 체크하는 배열
vector<int> a[5]; //첫 인덱스의 시작이 0이 아닌 1로 하기 위해서 8 크기의 벡터 생성

void bfs(int start)
{
    queue<int> q;
    q.push(start);
    c[start]=true;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        cout<<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()
{
    a[1].push_back(2);
    a[2].push_back(1);

    a[1].push_back(3);
    a[3].push_back(1);

    a[1].push_back(4);
    a[4].push_back(1);

    a[2].push_back(4);
    a[4].push_back(2);

    a[2].push_back(5);
    a[5].push_back(2);

    a[3].push_back(6);
    a[6].push_back(3);
    
    a[3].push_back(7);
    a[7].push_back(3);

    a[4].push_back(5);
    a[5].push_back(4);

    a[6].push_back(7);
    a[7].push_back(6);

    bfs(1);
}

 

순서를 생각하면서 코드를 보면 이해가 잘 된다.