[기본 개념] BFS(Breadth-First Search)

---

BFS(Breadth-First Search)

---

개요

 - 너비 우선 탐색의 기본 개념과 사용하는 상황, 구현 방식을 알아본다. 

---

기본 개념

 - 너비 우선 탐색은 루트 노드(임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다. 

 - 기본 개념만으로는 이해하기 힘든 부분이 있으니 아래 탐색 과정을 보면서 이해하자.

 

탐색 과정

  - 하기의 트리를 1번 노드(임의의 노드)부터 너비 우선 탐색하는 과정을 살펴보자.

 

1. 1번 노드를 탐색 대상으로 선정한다. 

 

2. 1번 노드를 탐색하고, 1번과 인접해 있는 노드들(다음 탐색 대상)을 조사한다. 

3. 2,3,4번 노드를 탐색하고 2,3,4번 노드와 인접해 있는 노드들(다음 탐색 대상)을 조사한다. 

 4. 5,6,7 노드를 탐색하고 5,6,7번 노드와 인접해 있는 노드들(다음 탐색 대상)을 조사한다.

 5. 다음 탐색 대상 노드가 없으므로 모든 노드 들의 탐색을 마쳤다고 판단하고, 탐색을 마친다.

BFS 사용 상황

 - 위 탐색 과정에서 봤듯이 BFS는 방문 노드의 인접한 노드부터 탐색하는 방식으로 탐색한 노드에 원하는 결과값이 있다면 바로 탐색을 마칠 수 있다는 장점이 있다. 이러한 장점은 최단 경로 혹은 임의의 경로를 찾기에 적합하다. 

 *BFS와 비교하여 DFS(깊이 우선 탐색,Depth-First Search)는 모든 노드를 방문한 후에 탐색을 종료한다. 때문에 BFS보다 느려 최단 경로 판단시에는 사용하지 않는 편이 좋다. 

 

구현 방식

 - BFS의 과정은 큐(Queue) 자료구조를 사용하여 구현할 수 있다. 

 * 큐(Queue): FIFO(First-In-First-Out, 선입선출)의 순서를 따르는 자료구조, 매표소에서 줄을 서는 사람들이 빠지는 형태와 같다.

 - 위에서 사용된 탐색 과정을 큐의 상태와 함께 보자

 

1. 1번 노드를 탐색 대상으로 선정한다. 

  ( 큐에 탐색 대상 노드 번호를 Push한다. )

 

2. 1번 노드를 탐색하고, 1번과 인접해 있는 노드들(다음 탐색 대상)을 조사한다. 

  ( 1번 노드를 큐에서 POP하여 탐색하고, 1번과 인접해 있는 노드들(다음 탐색 대상)을 큐에 Push한다. )

 3. 2,3,4번 노드를 탐색하고 2,3,4번 노드와 인접해 있는 노드들(다음 탐색 대상)을 조사한다. 

( 2,3,4번 노드를 큐에서 POP하여 탐색하고, 2,3,4번과 인접해 있는 노드들(다음 탐색 대상)을 큐에 Push한다. )

4. 5,6,7 노드를 탐색하고 5,6,7번 노드와 인접해 있는 노드들(다음 탐색 대상)을 조사한다.

( 5,6,7번 노트를 큐에서 POP하여 탐색하고, 5,6,7번과 인접해 있는 노드들(다음 탐색 대상)을 큐에 Push한다. )

 5. 다음 탐색 대상 노드가 없으므로 모든 노드 들의 탐색을 마쳤다고 판단하고, 탐색을 마친다.

 ( 큐에 탐색 대상 노드가 없으므로 탐색을 마친다. )

 의사 코드 (pseudocode)

void BFS(Node root){
    Queue q = new Queue();

    root.marked = true; // 방문했다는 표시를 한다. 같은 노드를 재탐색하는 동작을 방지한다. 
    q.push(root);

    while(q.isEmpty() == false){ // q가 비어있지 않을때 탐색을 진행한다.

        int qSize = q.size();

        for(int i=0; i<qSize; i++){
            Node temp = q.pop();
            temp.marked = true; 

            if(temp == 목표 노드) return; // 탐색을 한 노드가 목표한 노드라면 탐색을 마친다. 
            else{
                foreach(temp의 인접 노드){
                    if(temp의 인접 노드.marked == false){ // 방문하지 않은 인접 노드에 대해 탐색을 진행한다. 
                        temp의 인접 노드.marked = true;
                        q.push(temp의 인접 노드);
                    }
                }
            }
        }
    }
}