[Algorithm] BFS

BFS (Breadth First Search)

그래프나 다차원 배열에서 인접한 노드나 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

• 모든 노드를 방문하기 위해 사용
• 큐(Queue)를 사용하여 인접한 노드를 먼저 탐색
• 시간 복잡도: O(N) — 각 칸(노드)을 한 번씩만 방문

---

✅ BFS 기본 원리

1. 시작하는 칸을 큐에 넣어 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2 ~ 3번을 반복

방문 표시를 큐에 넣을 때 해주는 게 중요!
방문 체크 없이 큐에 넣으면 중복 방문 발생.

✅ 정석적인 구현 방법

거의 외우다시피 해도 괜찮음 !

const board = [
  [1, 1, 1, 0, 1, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 1, 0, 0, 0, 0, 0],
  [1, 1, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

const n = 7, m = 10;
const vis = Array.from({ length: n }, () => Array(m).fill(false)); // 방문 여부를 저장할 변수

// 상하좌우를 처리
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];

function bfs(startX, startY) {
  const queue = [];
  vis[startX][startY] = true; 
  queue.push([startX, startY]);  // 방문 표시를 하며 시작

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

    for (let dir = 0; dir < 4; dir++) {
      const [nx, ny] = [x + dx[dir], y + dy[dir]];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (vis[nx][ny] || board[nx][ny] !== 1) continue;

      vis[nx][ny] = true;
      queue.push([nx, ny]); // 큐에 추가
    }
  }
}

bfs(0, 0);

❗ 자주 하는 실수

• 시작 노드 방문 표시 안함
• 큐에 넣을 때가 아닌 큐에서 뺄 때 방문 표시함
• 범위 체크 조건 누락 (nx, ny)

---

✅ 백준 예제

BOJ 1926번 - 그림

1. 상하좌우로 연결된 그림의 크기를 알아내기
2. 도화지에 있는 모든 그림을 찾아내기

let [size, ...board] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [n, m] = size.split(" ").map(Number);
const visited = Array.from({ length: n }, () => Array(m).fill(false)); // 방문 여부를 저장할 변수
board = board.map((b) => b.split(" ").map(Number));

const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
let maxArea = 0;
let cnt = 0;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (visited[i][j] || board[i][j] == 0) continue;
    bfs(i, j);
    cnt++;
  }
}

function bfs(startX, startY) {
  const queue = [];
  visited[startX][startY] = true;
  queue.push([startX, startY]); // (0,0)에 방문 표시를 하며 시작
  let area = 0;
  while (queue.length > 0) {
    area++;
    const [x, y] = queue.shift();

    for (let dir = 0; dir < 4; dir++) {
      const nx = x + dx[dir];
      const ny = y + dy[dir];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (visited[nx][ny] || board[nx][ny] !== 1) continue;

      visited[nx][ny] = true;
      queue.push([nx, ny]); // 큐에 추가
    }
  }
  if (maxArea < area) maxArea = area;
}

console.log(cnt);
console.log(maxArea);

---

BOJ 2178번 - 미로 탐색 : 다차원 배열에서의 거리 측정

• 시작점과의 거리를 전부 계산
• 거리를 저장할 dist 배열을 두고 상하좌우의 칸을 볼 때 값을 잘 넣어주면 된다.
• 이 배열을 미리 -1로 초기화해두면 굳이 visited 배열을 따로 두지 않아도 방문 여부를 확인 가능

let [size, ...board] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, M] = size.split(" ").map(Number);
const dist = Array.from({ length: N }, () => Array(M).fill(-1)); // 거리를 저장할 변수
board = board.map((b) => b.split("").map(Number));

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

function dfs(startX, startY) {
  const queue = [];
  dist[0][0] = 0;
  queue.push([startX, startY]); // (0,0)에 방문 표시를 하며 시작

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

    for (let dir = 0; dir < 4; dir++) {
      const [nx, ny] = [x + dx[dir], y + dy[dir]];

      if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
      if (dist[nx][ny] !== -1 || board[nx][ny] !== 1) continue;

      dist[nx][ny] = dist[x][y] + 1;
      queue.push([nx, ny]);
    }
  }
}

dfs(0, 0);
console.log(dist[N - 1][M - 1] + 1);

---

BOJ 7576번 - 토마토

• BFS 시작 전 익은 토마토를 전부 큐에 넣는다
• 익지 않은 토마토는 dist = -1로 설정
• BFS 종료 후 dist에 남은 -1이 있으면 -1 출력

내가 푼 풀이 (시간초과)

// 모든 지점으로부터 거리를 구하는 문제
// 모든 시작점을 큐에 넣고 BFS를 돌리기
// 익은 토마토(시작점)는 큐에 넣고, 익지 않은 토마토는 dist -1로 둔다.

let [size, ...tomatos] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [m, n] = size.split(" ").map(Number);
const ripedDist = Array.from({ length: n }, () => Array(m).fill(0)); // 익거나 빈칸 -> 0
tomatos = tomatos.map((t) => t.split(" ").map(Number));

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

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (tomatos[i][j] == 1) queue.push([i, j]);
    else if (tomatos[i][j] == 0) ripedDist[i][j] = -1; // 익지 않은거 : -1
  }
}

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

  for (let dir = 0; dir < 4; dir++) {
    const [nx, ny] = [x + dx[dir], y + dy[dir]];

    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    if (ripedDist[nx][ny] >= 0) continue;

    queue.push([nx, ny]);
    ripedDist[nx][ny] = ripedDist[x][y] + 1;
  }
}

let day = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (ripedDist[i][j] == -1) return console.log(-1);
    day = Math.max(ripedDist[i][j], day);
  }
}

console.log(day);

수정 코드 -> shift 최적화 (시간 초과 해결)

let [size, ...tomatos] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [m, n] = size.split(" ").map(Number);
const ripedDist = Array.from({ length: n }, () => Array(m).fill(0)); // 익거나 빈칸 -> 0
tomatos = tomatos.map((t) => t.split(" ").map(Number));

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

for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (tomatos[i][j] == 1) queue.push([i, j]);
    else if (tomatos[i][j] == 0) ripedDist[i][j] = -1; // 익지 않은거 : -1
  }
}

let qIdx = 0;

while (qIdx < queue.length) {
  const [x, y] = queue[qIdx++];

  for (let dir = 0; dir < 4; dir++) {
    const [nx, ny] = [x + dx[dir], y + dy[dir]];

    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    if (ripedDist[nx][ny] >= 0) continue;

    queue.push([nx, ny]);
    ripedDist[nx][ny] = ripedDist[x][y] + 1;
  }
}

let day = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (ripedDist[i][j] == -1) return console.log(-1);
    day = Math.max(ripedDist[i][j], day);
  }
}

console.log(day);

---

이전에 정리해뒀던 포스팅을 참고하면 더욱 딥다이브할 수 있다 !

그래프 DFS/BFS

---

END