[ALPS Study] 탐색 - BFS(너비 우선 탐색)

BFS(Breadth First Search) :너비 우선 탐색

 -> 특정 정점에서 시작해서 인접한 노드를 먼저 탐색하는 방법

 

위 경우를 보자! DFS였다면 1-2-3-5-4-6-7 로 한 번 간 길은 끝까지 찍고 돌아오는 방식이다. 굳이 얘기하자면 깊고 좁은 느낌?

반면 BFS는 넓고 얕은 느낌이다! ((개인적)) 갈림길을 만나면 두 군데 모두 슝슝 간다. 

1->2 까지 왔을 때 3으로 가는 것이 아니라 또다른 갈림길인 4로 가는 것이다! 그 다음에는 2에서 갈림길인 3과 5를, 그 다음에는 4에서 갈림길인 6과 7을 방문하게 된다. 즉, 1-2-4-3-5-6-7 순서로 노드들을 방문하게 된다. 

 

그렇다면 BFS는 어떻게 구현할 수 있을까?

 

바로 Queue(큐) 이다! 큐는 선입선출형 자료구조를 뜻한다. 

   ----------------

<--    1 2 3 4    <--

   ----------------

 

이처럼 공간에 1, 2, 3, 4 순으로 넣으면, 나오는 것도 1, 2, 3, 4의 순서가 된다. 먼저 들어간 것이 먼저 나오는 것!

 

이것을 가지고 BFS를 어떻게 구현하느냐~~ 큐가 BFS에서 필요한 임시 저장 공간이 될 것 이 다 !

 

   -----------

<--    1     <--

   -----------

먼저 가장 처음 노드인 1번 노드를 큐에 넣는다.

 

<<1>>

   ------------------

<--     2   4     <--

   ------------------

그런 다음, 큐를 dequeue시켜서 1이 사라지게 된다.  그리고 1번 노드와 인접한 2번 4번 노드를 큐에 넣어준다.

 

<<1 - 2>>

   ------------------

<--     4   3   5     <--

   ------------------

다시 큐를 dequeue 하면 2가 뿅 튀어나오게 된다. 그리고 2번 노드와 인접한 3번 5번 노드를 큐에 넣어준다.

이어서 가보자

 

<<1 - 2 - 4>>

   ----------------------

<--     3   5   6   7    <--

   ----------------------

 

 

<<1 - 2 - 4 - 3>>

   ----------------------

<--     5   6   7    <--

   ----------------------

이제 3번 노드와 인접한 노드가 없기 때문에 쭉쭉 dequeue 해준다. 그러면

 

<<1 - 2 - 4 - 3 - 5 - 6 - 7>>

의 순서로 원소들을 탐색할 수 있다!

 

 

+ 유용한 STL

#include <queue> // 헤더파일 추가
//-queue : T type data를 contain 하는 선입선출(FIFO)형 자료구조

queue< T > name //과 같은 방식으로 선언
name.size() // name에 들어있는 원소의 수 반환
name.empty() // name이 비었다면 true, 원소 존재하면 false
name.front() // name의 첫번째 원소에 접근
name.push(T a) //name 가장 뒤에 a 추가(=enqueue)
name.pop() // name 가장 앞 원소 삭제

 

BFS 구현하기

 - NODE는 총 MAX개(0 ~ MAX-1 번)

간선의 정보는 adj라는 vector에 adj list로 저장됨

 

queue<int> q;
q.push(k);
visit[k] = 1;
while(!q.empty()){
	int cur = q.front();
    q.pop();
    for(int i=0; i<adj[cur].size(); i++){
    	if(visit[adj[cur][i]] == 0){
        	q.push(adj[cur][i]);
            visit[adj[cur][i]] = 1;
        }
    }
}