넓이 우선 탐색(BFS) 알고리즘

BFS(Depth-First Search) : 깊이 우선 탐색

• 그래프 완전 탐색

• 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

• FIFO 탐색 -> Queue 자료구조를 이용한다.

• 목표 노드에 도착하는 경로가 여러개일 때 최단경로를 보장한다.

BFS 동작 과정

---

BFS 기본 동작 방식

1. 방문여부 확인용 배열

BFS도 DFS와 마찬가지로 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.

예를들어 1~6의 노드를 가진 그래프가 있으면, boolean[] arr = new boolean[7]; 으로 배열을 만들어 준다.

( 0번 인덱스는 사용하지 않는다. )

해당 노드를 방문하면 해당 인덱스의 값을 TRUE로 바꿔준다.

2. 원본 그래프 -> 자료구조 초기화(인접리스트)

1. 시작할 노드를 정한다.

2. 각 노드에서 갈수있는 다른 노드를 확인 후 인접리스트로 초기화 한다.

3. 시작점을 정했기 때문에 시작점의 방문배열을 T로바꿔주고, Queue에 시작점을 더한다.

3. Queue 구현

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  // 큐에 삽입
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  // 큐에서 추출
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  // 현재 head가 가르키는 아이템
  peek() {
    return this.items[this.headIndex];
  }

  // 큐의 길이
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

4. Queue에서 노드를 꺼낸 노드의 인접노드를 Queue에 삽입

1. 맨 처음에 넣었던 노드1을 Queue에서 꺼낸다.

2. 꺼낸 노드 1의 인접노드(2,3)을 큐에 삽입한다.

3. 이 과정을 Queue가 비워질 때까지 반복한다.

5. 반복

1. 위에서 1을 꺼낸 뒤, 노드2,3을 넣은 상태이다.

2. dequeue(2) -> 2의 인접 리스트 5,6을 넣는다. enqueue(5), enqueue(6) -> 5, 6의 방문배열 True

3. dequeue(3) -> 3의 인접 리스트 4를 넣는다. enqueue(4) -> 4의 방문배열 True

4. dequeue(5) -> 5의 인접리스트는 없다.

5. dequeue(6) -> 6의 인접리스트는 없다.

6. dequeue(4) -> 4의 인접리스트는 없다.

결과적으로 탐색 순서는 [ 1 - 2 - 3 - 5 - 6 - 4 ]이다.

---

BFS 알고리즘 예제

예제) 백준 1697. 숨바꼭질

💡 문제 확인

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

💡 숨바꼭질 문제의 해법

초기 위치(N)에서 동생의 위치(M)에 도달하는 최단 시간을 계산하는 문제이고, 모든 순간이동(간선)의 비용이 1초로 동일하므로, BFS로 최단 시간을 계산할 수 있다

💡 숨바꼭질 문제 해결 코드

const MAX = 100001;
let n = 5; // 초기 위치(N)
let k = 17; //동생의 위치(K)
let visited = new Array(MAX).fill(0); // 각 위치까지의 최단 시간

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

function bfs() {
  // 너비 우선 탐색(BFS)
  queue = new Queue();
  queue.enqueue(n);
  while (queue.getLength() != 0) {
    // 큐가 빌 때까지 반복
    let cur = queue.dequeue();
    if (cur == k) {
      // 동생의 위치에 도달한 경우
      return visited[cur]; // 최단 시간 출력
    }
    for (let nxt of [cur - 1, cur + 1, cur * 2]) {
      // 공간을 벗어난 경우 무시
      if (nxt < 0 || nxt >= MAX) continue;
      // 아직 방문하지 않은 위치라면
      if (visited[nxt] == 0) {
        visited[nxt] = visited[cur] + 1;
        queue.enqueue(nxt);
      }
    }
  }
}
console.log(bfs());

---

📑 참고 자료

[Algorithm/Java] BFS(너비 우선 탐색)

백준 2606. 바이러스