BFS(너비우선탐색)

BFS(너비 우선 탐색)은 그래프나 트리에서 루트 노드(또는 시작 노드)로부터 가까운 노드부터 우선적으로 탐색하는 방식입니다.

큐(Queue) 자료구조를 기반으로 하며, 방문한 노드는 다시 방문하지 않도록 처리해야 합니다.

• DFS가 “깊게 → 백트래킹”
• BFS는 “가까운 것부터 → 점점 멀리” 탐색.

유형	설명
최단 거리/최소 횟수 문제	미로 탐색, 전염, 전파, 이동 횟수, 최소 변환 등
계층 구조 탐색	트리 레벨 순회, 위상 정렬
다익스트라 (특수 BFS)	가중치 1일 때 최단 거리 계산
시뮬레이션 문제	바이러스 전파, 불 퍼짐, 토마토 익히기 등

JavaScript로 구현: 인접 리스트 기반

const graph = [
  [],        // 0번 dummy
  [2, 3],    // 1 → 2, 3
  [4],
  [5, 6],
  [],
  [],
  [],
];

const visited = Array(graph.length).fill(false);

function bfs(start) {
  const queue = [start];
  visited[start] = true;

  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current);

    for (const next of graph[current]) {
      if (!visited[next]) {
        visited[next] = true;
        queue.push(next);
      }
    }
  }
}

bfs(1); // 시작 노드

자바스크립트의 경우 큐를 지원하지 않기 때문에 큐를 직접 구현해야한다.

ex)

class Queue {
  constructor() {
    this.q = [];
    this.head = 0;
  }

  enqueue(value) {
    this.q.push(value);
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    return this.q[this.head++];
  }

  isEmpty() {
    return this.q.length === this.head;
  }

  size() {
    return this.q.length - this.head;
  }
}

2차원 배열(Grid 기반 BFS)

const grid = [
  [1, 1, 0],
  [0, 1, 0],
  [1, 1, 1],
];
const visited = Array.from({ length: 3 }, () => Array(3).fill(false));

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function bfs(x, y) {
  const queue = [[x, y]];
  visited[y][x] = true;

  while (queue.length > 0) {
    const [cx, cy] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];

      if (
        nx >= 0 && nx < 3 &&
        ny >= 0 && ny < 3 &&
        grid[ny][nx] === 1 &&
        !visited[ny][nx]
      ) {
        visited[ny][nx] = true;
        queue.push([nx, ny]);
      }
    }
  }
}

bfs(0, 0);

주요특징

항목	설명
탐색 방향	너비 우선 (가까운 것부터)
사용 자료구조	큐 (Queue)
방문 체크 방식	visited 배열 사용
시간 복잡도	O(V + E)
특징	최단 거리 보장 (가중치 없을 때)