[BFS & DFS]BFS(Breadth First Search)

저번에 *DFS*에 대해서 공부하였으니까, 이번엔 BFS에 대해서 공부해봅시다.

저번에 봤던 것 처럼 BFS는 Breadth First Search라고 너비 먼저 탐색알고리즘이 되겠습니다.

BFS는 그럼 어떤 장단점이 있을까요???

BFS는 넓게 탐색하기 때문에 최단 경로를 찾는데에 용이합니다만,

목적지까지 모든 경우가 비슷한 거리를 가지면 안 좋을 수 있고, DFS와 마찬가지로 메모리 overflow가 일어날 수 있습니다(탐색 범위가 크면).

DFS를 봤던 것 처럼 BFS도 tree부터 살펴봅시다!!!

BFS

---

그림을 보니까 이해가 되시나요??? 이번엔 DFS와 다르게 자식들을 먼저 탐색하네요!!! 우물을 넓게 파는 알고리즘!?!?!? graph에서 보면 다음과 같습니다.

그림을 보면 이해가되시나요?? 위에 tree처럼 역시 넓게 탐색하네요ㅎㅎ

이번엔 DFS와 다르게 stack이 아닌 queue를 사용합니다. 왜냐면 DFS에서 노드를 탐색하면 자식 노드들을 stack에 push했었는데 왜 stack에 넣었는지 생각해봅시다.

stack은 LIFO(Last In First Out)의 성질이니까 맨 처음 넣었던 노드가 가장 마지막에 나오는 성질이잖아요. DFS의 경우는 깊게먼저 들어갔다가 나와야 하기 때문에 맨 첫번째로 들어간 자식은 가장 마지막에 나오겠죠.

그런데 이번엔 queue를 사용합니다!!! queue는 FIFO(First In First Out)으로 탐색된 노드의 자식들이 먼저 들어가면 먼저 나오겠죠??

제가 필력이 안좋아서..ㅎㅎㅎ 그림을 보면 이해가 되시는지 모르겠네요ㅎㅎ 자 그러면 한번 구현해봅시다!!!!

#include <iostream>
#include <queue>
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};
    queue<int> q;
    q.push(0);
    visit[0] = true;
    while(!q.empty()){
        int temp = q.front();
        cout << temp + 1 << " -> ";
        q.pop();
        for(int i=0; i<7; i++){
            if(map[temp][i] && !visit[i]){
                visit[i] = true;
                q.push(i);
            }
        }
    }
    cout << "end" << endl;
}

실행해보면 사진과 맞게 1 2 3 4 6 5 7 end 나오는걸 알 수 있습니다!!! 이렇게 간단하게 DFS, BFS를 마무리 하였습니다. 다시 정리해보면 이렇게 쓸 수 있겠네요ㅎㅎ

---

• DFS Depth First Search

1. 한 우물 먼저 다 파버리자!!!
2. Cycle Detection류의 문제에 사용!!
3. 그래프, 트리가 커지면 overflow 우려!!

• BFS Breadth First Search

1. 넓게 다 파버리자!!!
2. 최단 경로 탐색에 용이!!
3. overflow 우려!!!!

---