BFS

BFS란?

Breadth-First Search
너비 우선 탐색, 시작 노드에서 가까운 노드부터 차례대로 탐색하는 알고리즘
Queue 자료구조를 활용

BFS의 사용 목적

최단 거리 탐색
- 그래프에서 시작 노드와 도착 노드의 최소 이동 회수, 최단 경로 길이를 구할 때 사용
트리의 레벨 탐색
- 트리 구조에서 각 레벨별로 탐색이 필요할 때 사용
순차적 확장 탐색
- 시간, 단계, 거리 등 순서를 기준으로 범위를 넓혀가며 탐색

BFS 코드 문제

5 × 5 크기의 2차원 배열이 존재
각 칸의 값은 다음을 의미
- 1 : 지나갈 수 있는 길
- 0 : 지나갈 수 없는 길 (벽)
시작 위치는 (0, 0), 도착 위치는 (4, 4), 도달이 불가할 경우 "IMPOSSIBLE" 출력
목표: array[4][4]에 도달할 수 있는 최단 거리를 구하기

let maps = [
  [1, 0, 1, 1, 1],
  [1, 0, 1, 0, 1],
  [1, 0, 1, 1, 1],
  [1, 1, 1, 0, 1],
  [0, 0, 0, 0, 1],
];
let [x_end, y_end] = [maps.length - 1, maps[0].length - 1];
let dx = [1, 0, -1, 0];
let dy = [0, 1, 0, -1];
let queue = [[0, 0]];

while (queue.length !== 0) {
  let [dot_x, dot_y] = queue.shift();
  for (let i = 0; i < dx.length; i++) {
    let x = dx[i] + dot_x;
    let y = dy[i] + dot_y;

    if (x > x_end || x < 0 || y > y_end || y < 0) continue;
    if (maps[x][y] !== 1) continue;
    queue.push([x, y]);
    maps[x][y] += maps[dot_x][dot_y];
  }
}

console.log(maps[x_end][y_end] !== 1 ? maps[x_end][y_end] : "IMPOSSIBLE");

note

dx, dy와 같은 경우, 다음 탐색할 배열의 위치 값을 미리 좌표별로 저장해둔다.
queue를 통해 해당 탐색 위치에서 다음 탐색이 가능한 위치들을 저장해 나간다.
초기 위치는 (0, 0)이기 때문에, 이 값을 먼저 queue에 넣어둔다.

while문을 통해 queue가 빌 때까지 탐색한다. 즉, 더 이상 다음 탐색 경로가 없을 경우 멈춘다.
queue에 저장된 위치값들을 하나씩 꺼내면서, 앞서 선언한 dx, dy를 이용해 아래, 오른쪽, 위, 왼쪽 순으로 탐색을 진행한다.

조건문을 통해 다음 탐색할 배열의 위치에 대한 예외 처리를 해준다.
즉, 배열 인덱스가 유효하지 않거나, 원하지 않는 조건일 경우 해당 방향은 건너뛴다.

// 출력
[
  [3, 0, 9, 10, 11],
  [2, 0, 8, 0, 10],
  [3, 0, 7, 8, 9],
  [4, 5, 6, 0, 10],
  [0, 0, 0, 0, 11],
];

위 배열은 BFS 탐색이 끝난 후의 maps 배열이며, 각 숫자는 시작점에서 해당 위치까지 도달하는 데 걸린 최단 누적 거리 값을 표현
시작점 (0,0)은 1로 시작하고, 한 칸씩 이동할 때마다 누적되어 갱신.

BFS 추천 알고리즘 문제집

BFS 알고리즘 문제 - 백준

BFS란?​

BFS의 사용 목적​

BFS 코드 문제​

BFS란?

BFS의 사용 목적

BFS 코드 문제