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

※ 그래프 용어

  - 정점(vertex) : 그래프 안의 노드

  - 간선(edge) : 각 정점을 잇는 선

  - 인접(adjacent) : 간선으로 연결된 정점

  - 이웃(neighbor) : 인접한 정점

 

BFS(Breadth First Search)로 줄여 부르는 너비 우선 탐색은 그래프를 탐색하는 방법이다. 

깊이 우선 탐색과 달리 너미 우선 탐색은 재귀를 쓰지 않는다. 대신 큐로 문제를 해결한다. 큐는 FIFO로 먼저 들어간 데이터를 우선 처리한다.

 

* 너비 우선 순회 알고리즘

1. 그래프 내 아무 정점에서 시작한다. 이 정점을 "시작 정점"이라 부른다.

2. 시작 정점을 방문 배열에 추가해 방문 표시를 한다.

3. 시작 정점을 큐에 추가한다.

4. 큐가 빌 때까지 실행하는 루프를 시작한다.

5. 루프 안에서 큐의 첫 번째 정점을 꺼내온다. (삭제) 이 정점을 "현재 정점"이라 부른다.

6. 현재 정점의 인접 정점들을 순회한다.

7. 이미 방문한 인접 정점이면 무시한다.

8. 아직 방문하지 않은 인접 정점이면 방문 배열에 추가해 방문 표시 후 큐에 추가한다.

9. 큐가 빌 때까지 루프(4단계부터)를 반복한다.

 

* 코드 구현

    void BFS(int v) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(v);
        visited[v] = true;

        while (!Q.isEmpty()) {
            v = Q.poll();
            System.out.print(v+" ");
            for (int i=1; i<=N; i++) {
                if (visited[i]) continue;//방문한 정점이면 스킵
                if (A[v][i] == 0) continue;//값이 0이면 간선이 없으므로 스킵
                Q.offer(i);
                visited[i] = true;//확산한 정점을 방문처리
            }
        }
    }

 

* BFS vs DFS

상황에 따라 다른 알고리즘을 선택해야 한다.

너비우선탐색은 시작 정점과 가장 가까운 정점을 모두 순회한 다음 멀어진다.

깊이우선탐색은 즉시 시작 정점과 최대한 멀어진다. 탐색이 막히면 그제서야 시작 정점으로 돌아온다.

 

SNS에서 어떤 사람과 직접 관계된 사람을 찾는 문제에서 앨리스의 진짜 친구만 (친구의 친구가 아닌) 찾고 싶을 때는 BFS를 사용하면 바로 찾을 수 있다. 하지만 DFS를 사용하면 친구의 친구까지 검색 후 다시 돌아오기 때문에 훨씬 오래 걸린다.

 

가계도에서 루비의 증손주인 루스를 찾는 문제에서 DFS를 사용하면 바로 찾을 수가 있지만, BFS를 사용하면 관계없는 친척들까지 순회한 다음 증손주를 확인할 수 있다.

 

+결론

그래프를 탐색하는 동안 시작 정점 가까이 있고 싶은가 아니면 무조건 멀리 떨어지고 싶은가.

가까이 있고 싶다면 너비우선탐색이 좋고, 빨리 멀어져야 한다면 깊이우선탐색이 이상적이다.

 

* BFS 문제 유형

1. 미로가 주어지고 목적지까지 가는 최단거리 구하는 문제

  - map[][]이 주어질 때, 탐색을 해서 map[A][B] -> map[A][C]로 이동할 때마다 map[A][B]까지 이동한 누적거리 + 1을 해서 map[A][C]에 저장한다.

  - 이런 식으로 거리값을 업데이트 해나가면 이미 방문한 정점은 지나치기 때문에 최단거리를 구할 수가 있다.

  ex) A[nx][ny] = A[tmp.x][tmp.y] + 1;