알고리즘 | 너비 우선 탐색 BFS 알고리즘 - 그래프 탐색

너비 우선 탐색 (BFS)으로 그래프를 탐색해보자.

그래프 탐색

하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다.

특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다.

너비 우선 탐색 BFS

BFS는 그래프에서 넓게 우선적으로 탐색하는 알고리즘이다.

깊이 우선 탐색 (DFS)은 스택(stack)을 사용하지만, 너비 우선 탐색 (BFS)은 큐(queue)를 사용한다.

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.
• DFS보다 빠르지만 복잡하다.
• 어떤 노드를 방문했는지 검사해야한다.

BFS의 동작 방식

• 자신과 인접한 노드를 전부 queue에 넣는다.
• queue에 들어있는 노드들을 앞에서 shift해서 꺼내어 또 그 노드가 인접한 노드들을 전부 queue에 넣는다.
• 이 과정은 queue에 들어있는 노드가 없을 때 까지 반복한다.

그래프 탐색 예제

백준 1260 https://www.acmicpc.net/problem/1260

아래와 같은 그래프가 있을 때, BFS로 방문해 보자.

정점 5개, 간선 5개, 3번부터 탐색 시작

• 정점은 1~5번 노드가 존재한다.
• 간선은 서로 다음과 같이 연결되어 있다.

• 출발 노드는 3번 노드이다.

다음은 그래프의 방문 순서를 표현한 것이다.

노란색은 현재 탐색하는 노드, 회색은 이미 방문한 노드, 하얀색은 방문하지 않은 노드다.

(1) 현재 탐색 노드 == 3

노드 3을 탐색하였으므로 방문 처리한다.

queue에 3을 넣는다. 

queue에서 3을 dequeue해주어서 3과 인접한 노드를 처리한다.

3과 인접한 1, 4 노드는 방문하지 않았으므로, 방문을 진행할 것이다.

(2), (3)은 인접한 노드를 방문하는 과정으로 dequeue를 진행하지 않는다.

(2) 현재 탐색 노드 == 1

노드 1를 탐색하였으므로 방문 처리한다.

queue에 1을 넣는다. 

1을 탐색하였으므로 3과 인접한 4를 방문한다. 

(3) 현재 탐색 노드 == 4

노드 4를 탐색하였으므로 방문 처리한다.

queue에 4를 넣는다.

이후 노드3과 인접한 노드 중 더이상 방문할 노드가 없으므로 다음 노드의 인접한 노드를 탐색한다.

(4) 현재 탐색 노드 == 2

queue에서 1를 dequeue해주어서 1와 인접한 노드를 처리한다.

노드1과 인접한 노드는 3, 2번 노드다.

노드3은 이미 방문하였으므로, 노드2를 탐색한다.

노드 2을 탐색하였으므로 방문 처리한다.

queue에 2를 넣는다.

이후 노드1과 인접한 노드 중 더이상 방문할 노드가 없으므로 다음 노드의 인접한 노드를 탐색한다.

(5) 현재 탐색 노드 == 5

queue에서 4를 dequeue해주어서 4와 인접한 노드를 처리한다.

노드 4와 인접한 노드는 3, 5번 노드다.

노드3은 이미 방문하였으므로, 노드5를 탐색한다.

노드 5을 탐색하였으므로 방문 처리한다.

queue에 5를 넣는다.

이후 노드4와 인접한 노드 중 더이상 방문할 노드가 없으므로 다음 노드의 인접한 노드를 탐색한다.

(6) 현재 탐색 노드 == 2

queue에서 2를 dequeue해주어서 2와 인접한 노드를 처리한다.

노드 2와 인접한 노드는 21,5번 이지만 전부 이미 방문했으므로 탐색할 노드가 없다.

(7) 현재 탐색 노드 == 5

queue에서 5를 dequeue해주어서 5와 인접한 노드를 처리한다.

노드 5와 인접한 노드는 2,4번 이지만 전부 이미 방문했으므로 탐색할 노드가 없다.

queue의 길이가 0이되어 탐색을 종료한다.

위와 같은 알고리즘을 자바스크립트 코드로 작성하면 다음과 같다.

function BFS을 참고하면 된다.

 function solution(n, m, v, road) {
    let graph = Array.from(Array(n + 1), () => Array());
    let ch = Array(n + 1).fill(0);
    let answer = [];

    // 연결된 노드 표시하기
    for (let i = 0; i < m; i++) {
      graph[road[i][0]].push(road[i][1]);
      graph[road[i][1]].push(road[i][0]);
    }
    // 연결된 노드를 오름차순으로 정렬하기
    for (let i = 1; i <= n; i++) {
      graph[i].sort((a, b) => a - b);
    }

    // BFS로 그래프 탐색
    function BFS() {
      let queue = [];
      ch[v] = 1;
      answer.push(v);
      queue.push(v);

      while (queue.length) {
        let cur = queue.shift();
        for (let node of graph[cur]) {
          if (ch[node] === 0) {
            answer.push(node);
            ch[node] = 1;
            queue.push(node);
          }
        }
      }
    }

    BFS();
    return answer;
  }
  console.log(
    solution(4, 5, 1, [
      [1, 2],
      [1, 3],
      [1, 4],
      [2, 4],
      [3, 4],
    ])
  ); // [ 1, 2, 3, 4 ]
  console.log(
    solution(5, 5, 3, [
      [5, 4],
      [5, 2],
      [1, 2],
      [3, 4],
      [3, 1],
    ])
  ); // [ 3, 1, 4, 2, 5 ]
  console.log(
    solution(1000, 1, 1000, [
      [999, 1000],
      [999, 1000],
    ])
  ); // [ 1000, 999 ]

참고
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html