[개념 정리] BFS(너비 우선 탐색)

너비 우선 탐색이 뭘까?

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

너비 우선 탐색

너비 우선 탐색인 BFS(Breath Frist Search)는 그래프를 탐색하는 알고리즘으로, 한 정점에서 시작해 다음 깊이의 정점으로 이동하기 전에 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다.

즉, BFS는 계층별로 레벨별로 탐색을 한다는 의미입니다.

 

주로 같은 가중치를 가진 그래프에서 최단 거리 알고리즘으로 사용됩니다.

 

BFS는 아래 그림의 순서로 탐색합니다.

탐색 순서는

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 가 됩니다. 

 

너비 우선 탐색의 수도 코드를 알아볼까요?

 

너비 우선 탐색의 수도 코드는 2개가 존재합니다.

 

첫번째 수도 코드는 아래와 같습니다.

BFS(G, u)
        u.visited = true
        q.push(u);
        while(q.size())
               u = q.front()
               q.pop()
               for each v ∈ G.Adj[u]
                     if v.visited == false
                            v.visited = true
                            q.push(v)

 

각 수도 코드가 가지는 의미는 다음과 같습니다.

 

1. 시작 지점인 u 정점을 방문 처리를 하고 큐에 푸시합니다.

2. q.size()만큼 while 반복문을 돌면서 큐 앞단의 있는 u 정점을 뺀 뒤, u 정점과 연결된 인접한 노드들을 탐색합니다.

3. u 정점과 연결된 인접한 노드들 중 아직 방문하지 않은 정점을 방문처리 하고, 큐에 푸시를 합니다.

 

 

두번째 수도 코드는 아래와 같습니다.

BFS(G, u)
        u.visited = 1
        q.push(u);
        while(q.size())
               u = q.front()
               q.pop()
               for each v ∈ G.Adj[u]
                     if v.visited == 0
                            v.visited = u.visited + 1
                            q.push(v)

 

두번째 수도 코드는 주로 가중치가 같은 그래프 내에서 최단 거리를 구하는 알고리즘으로 사용됩니다.

최단 거리의 값을 알아야 하기 때문에 방문 처리를 최단거리 배열을 사용해서 해줍니다.

 

방문시 1씩 더해주면 어떻게 될까요? 

 

아래 그림과 같이 됩니다.

1번 노드의 거리는 0이 되고,

2번, 3번, 4번 노드의 거리는 1이 되고,

5번, 6번, 7번, 8번 노드의 거리는 2가 됩니다.

 

정말 그런지, 코드로 확인해 보겠습니다.

 

BFS를 구현한 코드는 아래와 같습니다.

private static void bfs() {

    int[] visited = new int[9];

    Arrays.fill(visited, -1);
    visited[0] = 0;
    Queue<Integer> queue = new LinkedList<>();

    queue.add(0);

    while(!queue.isEmpty()) {
        int cur = queue.poll();

        System.out.println(cur + "번째 노드, 거리 : " + visited[cur]);

        for(int next : graph.get(cur)) {
            if(visited[next] == -1) {
                visited[next] = visited[cur] + 1;
                queue.add(next);
            }
        }
    }
}

 

실행을 해보면 결과는 다음과 같이 나옵니다.

 

출력해본 결과 그림과 같은 결과가 나옵니다.

 

만약, 시작 지점이 하나가 아닌 다수인 경우는 어떻게 될까요?

 

시작 지점이 다수인 겨우라면 처음 큐에 푸쉬하는 지점도 다수가 되어야 하고, 해당 지점의 visited를 모두 1로 만들면서 시작해야 합니다.

 

 

DFS와 BFS의 차이점은 뭘까요?

 

알고리즘	특징
DFS	메모리를 덜 사용합니다. 절단점을 구할 수 있습니다. 코드가 더 짧고, 완전 탐색에서 많이 사용됩니다.
BFS	메모리를 더 사용합니다. 가중치가 같은 그래프내에서 최단거리를 구할 수 있습니다. 코드가 깁니다.

 

 

코딩 테스트 문제에서 "퍼져나간다, 탐색한다"와 같은 글자가 있는 경우 반드시 DFS와 BFS가 생각 나야 합니다.