너비 우선 탐색 (Breadth-First Search)

1. 너비 우선 탐색이란?

루트 노드 ( 혹은 다른 임의의 노드 )에서 시작하여 인접한 노드를 먼저 탐색하는 방법.

시작 노드로부터 가장 가까운 노드를 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법.

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.

깊이 우선 탐색보다 좀 더 복잡하다.

그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

검사하지 않으면 무한 루프에 빠질 수 있다.

방문한 노드들을 차례로 정장한 후 꺼낼 수 있는 자료 구조인 Queue를 사용한다.

즉, 선입선출(FIFO) 원칙으로 탐색.

 

2. 사용처

최단 거리를 구해야하는 경우.

너비 우선 탐색은 현재 노드에서 가까운 곳부터 찾기 때문에, 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다.

 

날짜를 계산하는 문제.

전염병 확산 기간 등 날짜를 구해야 할 경우.

깊이 우선 탐색으로 날짜를 탐색할 경우, 다른 경로에 동일한 날짜에 감염된 환자가 있어 나중에 다른 경로를 탐색할 때

다시 동일한 날짜가 계산되기에 비효율적이다.

 

1. 시작 노드를 큐에 넣고 시작한다.
   큐에 들어간 노드들은 방문 처리를 한다.
2. 큐에 있는 노드를 뽑아, 시작 노드로 바꿔주고 인근 노드들을 큐에 넣어준다.
   마찬가지로 큐에 들어간 노드들은 방문 처리를 한다.
3. 큐가 비어질 때까지 반복한다.

 

3. 그림

 

 

4. 코드

노드 0을 기준으로 탐색

public class BreadthFirstSearch {
    static private LinkedList<Integer> list[] = new LinkedList[5];

    public static void main(String[] args){
        for (int i = 0; i < list.length; i++) {
            list[i] = new LinkedList<>();
        }

        list[0].add(1);
        list[0].add(2);
        list[0].add(4);
        list[1].add(0);
        list[1].add(2);
        list[2].add(0);
        list[2].add(1);
        list[2].add(3);
        list[2].add(4);
        list[3].add(2);
        list[3].add(4);
        list[4].add(0);
        list[4].add(2);
        list[4].add(3);

        solution(0);
    }

    public static void solution(int start){
        boolean visited[] = new boolean[5];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.add(start);

        while (queue.size() > 0){
            start = queue.poll();
            System.out.print(start + " ");

            Iterator<Integer> iterator = list[start].listIterator();
            while (iterator.hasNext()){
                int near = iterator.next();

                if(!visited[near]) {
                    visited[near] = true;
                    queue.add(near);
                }
            }
        }
    }
}