[알고리즘] BFS (너비우선탐색)

1. BFS (너비 우선 탐색)?

BFS(Breadth-First-Search)는 너비 우선 탐색으로 큐(FIFO:선입선출)를 통해서 주로 구현이 됩니다. 출발 노드에서 가까운 것부터 접근하는 방식으로, 넓게, 층층히 탐색한다고 생각할 수 있습니다. 최단경로, 임의경로를 탐색해야하는 문제에서 주로 사용됩니다. DFS와 마찬가지로 방문체크를 해줄 필요가 있으며, 방문 체크를 하지 않을 경우 무한루프에 빠질 수 있습니다.

 

예시로 사용될 그래프

---

2. 기본적인 원리

기본적인 동작 원리는 다음과 같습니다.

1. 현재 노드와 연결된 노드 중 방문되지 않은 모든 노드에 대해 방문체크 후 큐에 삽입
2. 큐에서 가장 앞의 노드(가장 먼저 삽입된 노드) pop -> 새 노드
3. 새 노드에 대해 1번 반복
4. 큐에 원소가 없을 때까지 1~3 반복

 

처음에 시작노드를 큐에 삽입하고 방문처리 합니다. 그럼 큐에 시작 노드 0이 들어가있는 상태가 됩니다. 

이제 본격적으로 bfs를 시작하게 되는데, 우선 큐에 있는 노드 중 가장 앞의 노드를 pop합니다. 현재 큐에는 0 하나만 있을테니 0이 pop됩니다.

pop된 노드(0번 노드)에 대해 인접노드들을 확인합니다.

2개의 인접노드가 있으니, 2개의 인접노드가 기존에 방문된 적이 있는지 확인합니다. 방문된 적이 없음을 확인했으니, 큐에 삽입해주고, 방문을 체크해줍니다.

이런식으로 모든 노드에 대해 진행되게 됩니다. 전체 과정을 그림으로 표시해 보겠습니다.

 

 

---

3. 정리

• 큐를 통해 다음 탐색할 모든 노드를 저장합니다. 따라서 메모리 사용량 증가합니다.
• 구현은 주로 스택을 사용하므로 직관적이지 않고, DFS보다 어렵습니다.
• 단순 경로 검색 속도는 DFS보다 빠릅니다. 또한, 최단경로 문제에 최적화된 알고리즘입니다.
• 너비를 우선 탐색하므로 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장합니다.

---

4. 간단한 코드 (Java)

import java.util.LinkedList;

public class BFS {
    static boolean[] visited = new boolean[6]; // 방문여부 저장 배열
    static LinkedList<Integer> queue = new LinkedList(); // 노드번호를 저장할 큐

    // 그래프 matrix로 표현
    static int[][] matrix = {{0,1,1,0,0,0},
                             {1,0,0,1,1,0},
                             {1,0,0,0,1,1},
                             {0,1,0,0,1,0},
                             {0,1,1,1,0,1},
                             {0,0,1,0,1,0}};


    public static void main(String[] args){
        queue.offer(0); // 초기에 큐에 0 삽입
        visited[0] = true; // 0의 방문여부 true

        System.out.print("BFS 탐색 순서: ");

        while(!queue.isEmpty()){ // 큐가 빌 때까지
            int popped = queue.pop(); // 큐의 첫 번째 노드 pop

            System.out.print(popped+" -> ");

            for(int i = 0 ; i < matrix.length; i++){ // popped의 인접노드에 대하여
                if(matrix[popped][i] == 1 && !visited[i]){ // 방문되어있지 않다면
                    visited[i] = true; // 방문체크
                    queue.offer(i); // 큐에 삽입
                }
            }
        }


    }
}

 

 

---

 

연관 게시글

• DFS(깊이우선탐색이란?) : [알고리즘] DFS(깊이우선탐색)

 

참고

• gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html