[Algorithm] 완전탐색 - BFS

BFS 이란 ?

Breadth-First-Search의 약어로, 가까운 곳부터 우선적으로 탐색하는 알고리즘이다. 

 

그래프 알고리즘에서 기초가 되는 탐색 방식이다.

---

BFS 특징 ?

BFS의 특징 몇 가지를 알아보자.

 

• 문제의 유형에 따라 데이터 저장 방법이 인접 행렬과 인접리스트로 나뉜다.
• 문제의 유형에 따라 데이터의 접근 방법이 달라진다.
• 인접한 곳부터 먼저 탐색을 진행한다.
• 큐의 자료구조를 이용하여 구현한다.
• 가중치가 없는 최단 경로, 위상 정렬에 활용된다.

---

BFS 구현 순서 ?

시작점과 방문 순서를 주의하며, 아래와 같은 순서를 잘 따르자.

 

1. 시작 노드를 큐에 삽입 후 방문 처리한다.
2. 큐에서 노드를 꺼낸다.
3. 꺼낸 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리한다.
4. 큐가 빌 때까지 2~3번 동작을 반복적으로 수행한다.

---

BFS 그림으로 살펴보기

[ 그래프 정보 ]

 

                   [ 큐 :  2, 4 ]                                        [ 큐 :  4, 3, 5 ]                                      [ 큐 :  3, 5 ]

                  [ 큐 :  5 ]                                             [ 큐 :  X ]                                             [ 큐 :  7 ]

[ 탐색 완료 ]

방문 순서 : 1 → 2 → 4 → 3 → 5 → 6 → 7

 

방문 종료 순서 : 1 → 2 → 4 → 3 → 5 → 6 → 7

---

BFS 시간복잡도

모든 곳을 탐색해야 하므로 노드의 확인 곧 시간복잡도와 직결된다.

 

문제 유형에 따라 BFS의 시간복잡도를 알아보자.

 

인접행렬 : O(가로 * 세로)

인접리스트 : O(노드 + 간선)

---

소스코드

// BFS 소스코드

public class BFS {

    // BFS 함수 정의
    static void bfs(int node, int[][]graph, boolean[]visited, Queue<Integer> qu) {
        
        // 시작 노드 삽입
        qu.offer(node);
        System.out.print(node+" ");
        
        // 현재 노드 방문 처리
        visited[node] = true;

        // 큐가 빌 때까지 반복
        while(!qu.isEmpty()) {
        
            // 큐에서 하나의 노드 꺼내기
            node = qu.poll();
            
            // 해당 노드와 연결된 노드 확인
            for(int idx=0; idx<graph[node].length; idx++) {
                int nextNode = graph[node][idx];
                
                // 연결된 노드 중 아직 방문하지 않은 노드가 존재할 경우
                if(visited[nextNode] != true) {
                
                	// 큐에 삽입
                    qu.offer(nextNode);
                    System.out.print(nextNode+" ");
                    
                    // 방문 처리
                    visited[nextNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
    
        // 연결 정보 그래프로 표현
        int [][] graph = {{},{2,3,8},{1,7},{1,4,5},{3,5},{3,4},{7},{2,6,8},{1,7}};
       
        // 방문 여부 확인 배열
        boolean [] visited = new boolean[graph.length];
        
        // 큐 선언, 생성 및 할당
        Queue<Integer> qu = new LinkedList<>();

        // bfs 함수 호출
        bfs(1,graph,visited,qu);

        // 탐색 순서 : 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
    }
}

---

BFS 주의 사항 ?

BFS를 구현할 때 3가지의 주의 사항이 존재한다.

 

• 시작점의 방문 처리 꼭 하기 → 미방문 처리 시 시작점을 두 번 방문하게 된다.
• 큐에 넣을 때 방문 처리 진행하기 → 큐에서 빼면서 처리할 경우 같은 곳이 여러 번 삽입되어 시간초과를 발생시킨다. 
• 탐색 범위를 전체 크기에서 벗어나지 않도록 하자. → 범위를 벗어날 경우 중간에 멈추거나, 이상한 결과를 출력한다.

---

요약

• BFS는 가까운 곳부터 우선적으로 탐색하는 알고리즘이다. 
• 인접행렬, 인접리스트 두 가지 유형으로 데이터를 저장될 수 있다.
• 큐의 자료구조를 사용한다.
• 시간복잡도는 O(가로 * 세로) 또는 O(노드 + 간선) 이다.
• 구현 시 시작점, 방문 순서에 대해 주의하자.