BFS / DFS

가로 3칸, 세로 2칸짜리 작은 지도에서 왼쪽 위 S로부터의 거리를 물결처럼 구해 봅니다. .은 지나갈 수 있는 칸, #은 벽입니다.

S . .
. # .

대기 줄(큐)에 시작 칸만 넣고, 앞에서부터 하나씩 꺼내며 이웃을 넣습니다.

완성된 거리표입니다. 오른쪽 아래로 가려면 벽을 돌아가야 하므로 3이 나옵니다.

0 1 2
1 # 3

여기서 두 가지를 확인해 두세요. 첫째, 거리는 큐에 넣는 순간 확정했습니다. 꺼낼 때 확정하면 (1,1) 자리처럼 여러 이웃이 같은 칸을 중복해서 큐에 넣습니다. 둘째, 대기 줄에서 꺼낸 순서가 거리 순서(0, 1, 1, 2, 3)라서 처음 도달한 값이 곧 최단 거리입니다.

격자 최단 거리 BFS는 다음 다섯 단계가 전부입니다.

1. 거리표를 -1로 채우고 시작점만 0으로 둡니다. -1이 "아직 방문 안 함" 표시를 겸합니다.

const dist = Array.from({ length: n }, () => Array(m).fill(-1));
dist[sr][sc] = 0;

2. 대기 줄을 배열로 만들고, 앞을 가리키는 인덱스를 따로 둡니다. shift()는 매번 전체를 당기므로 쓰지 않습니다.

const queue: [number, number][] = [[sr, sc]];
let head = 0; // head++로 O(1) 꺼내기

3. 네 방향은 배열 두 개로 표현합니다.

const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1];

4. 꺼낸 칸의 이웃마다 경계 → 벽 → 방문 순으로 걸러냅니다.

if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; // 지도 밖
if (grid[nr][nc] === 0 || dist[nr][nc] !== -1) continue; // 벽이거나 이미 옴

5. 거리를 확정하고 대기 줄에 넣습니다. 이 두 줄은 항상 붙어 다녀야 합니다.

dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);

전체 코드 — 시작점에서 모든 칸까지의 최단 거리:

function bfs(grid: number[][], sr: number, sc: number): number[][] {
  const n = grid.length, m = grid[0].length;
  const dist = Array.from({ length: n }, () => Array(m).fill(-1)); // 1단계
  const queue: [number, number][] = [[sr, sc]];
  let head = 0;              // 2단계: shift() 금지 — head 인덱스로 O(1) dequeue
  dist[sr][sc] = 0;
  const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1];                    // 3단계
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (let d = 0; d < 4; d++) {
      const nr = r + dr[d], nc = c + dc[d];
      if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;         // 4단계: 경계
      if (grid[nr][nc] === 0 || dist[nr][nc] !== -1) continue;      //        벽·방문
      dist[nr][nc] = dist[r][c] + 1;   // 5단계: 큐에 넣을 때 확정 — 중복 방문 차단
      queue.push([nr, nc]);
    }
  }
  return dist;
}

• 입력이 격자(2차원 배열)나 연결 관계(간선 목록·인접 리스트) 로 주어지고 "이동", "연결", "퍼진다"는 말이 나오면 이 유형입니다.
• "최소 몇 번에", "가장 빨리", "며칠 만에" — 한 번 이동의 비용이 전부 같다면 BFS입니다. 답은 도달한 레벨 그 자체입니다.
• "몇 덩어리인가", "가장 큰 영역", "갈 수 있나" — 거리와 무관하므로 DFS가 편합니다.
• 대표 상황: 미로 최단 경로, 섬(연결 영역) 개수와 크기, 전염·불길이 퍼지는 시뮬레이션, 모든 시작점에서 동시에 퍼지는 확산.

무엇을 구하느냐가 선택 기준입니다.

DFS로 연결 영역의 크기를 재는 형태입니다.

// 섬(연결 영역) 크기 재기
function dfs(grid: number[][], r: number, c: number): number {
  if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return 0;
  if (grid[r][c] !== 1) return 0;
  grid[r][c] = 2;                       // 방문 표시 (또는 visited 배열)
  return 1 + dfs(grid, r-1, c) + dfs(grid, r+1, c)
           + dfs(grid, r, c-1) + dfs(grid, r, c+1);
}

자주 나오는 BFS 변형 두 가지입니다.

• 다중 시작점 BFS: 시작점을 처음부터 전부 큐에 넣고 시작합니다("모든 바이러스에서 동시에 퍼짐"). 거리표에는 가장 가까운 시작점까지의 거리가 자동으로 들어갑니다.
• 레벨 단위 처리: 반복문 안에서 현재 큐 길이만큼만 끊어 돌면 "몇 턴째"를 셀 수 있고, 턴마다 추가 작업(예: 남은 칸 수 확인)을 끼워 넣을 수 있습니다.

"모든 경우를 시도하고 되돌아오기"까지 가면 백트래킹(별도 토픽)입니다.

• BFS 방문 표시를 꺼낼 때 함 — 같은 칸이 큐에 중복으로 쌓여 시간·메모리가 폭발합니다. 반드시 넣을 때 표시합니다.

queue.push([nr, nc]);                            // 잘못 — 표시 없이 넣음
const [r, c] = queue[head++]; visited[r][c] = true; //        꺼낼 때 표시

dist[nr][nc] = dist[r][c] + 1;  // 고침 — 넣는 순간 확정
queue.push([nr, nc]);

• 최단 거리 문제를 DFS로 풂 — DFS가 먼저 도착한 경로는 최단이 아닐 수 있습니다.
• shift() 사용 — O(N)이라 큰 격자에서 시간 초과입니다. head 인덱스를 쓰세요.
• 4방향 배열 오타 (dr/dc 짝 어긋남) — 한 번 정한 형태를 복사해 씁니다.

const dr = [-1, 1, 0, 0], dc = [0, 0, 1, -1]; // 짝이 어긋나도 컴파일은 됩니다

• 재귀 DFS의 깊이: 좌표 10⁵급 격자는 콜 스택 초과 위험이 있으므로 명시적 스택으로 전환합니다.

• 왜 BFS가 최단을 보장하는가: 큐는 들어간 순서대로 나오고, 거리 d인 칸은 거리 d-1인 칸에서만 만들어집니다. 따라서 큐 안의 원소는 항상 거리 d 아니면 d+1 두 종류뿐이고(비내림차순), 어떤 칸에 처음 도달했을 때의 거리가 곧 최솟값입니다. 이 성질은 간선 비용이 모두 같을 때만 성립합니다.
• 비용이 다르면 다른 도구: 간선마다 비용이 다르면 다익스트라(우선순위 큐), 비용이 0과 1 두 종류뿐이면 0-1 BFS(덱의 앞/뒤로 넣기)를 씁니다. BFS를 그대로 쓰면 틀립니다.
• 상태 그래프 BFS: 칸이 곧 정점일 필요는 없습니다. "현재 위치 + 열쇠 보유 상태", "현재 단어", "남은 연료"처럼 문제의 상태 전체를 하나의 정점으로 보면 방문 배열이 다차원이 됩니다(visited[r][c][key]). 단어 사다리류가 여기에 해당합니다.
• 복잡도: 정점 V, 간선 E일 때 두 방법 모두 O(V + E)이고, N×M 격자에서는 O(N×M)입니다. 각 칸은 방문 표시 덕분에 정확히 한 번씩만 큐에 들어갑니다.
• 재귀 DFS를 스택으로 바꾸기: 재귀 호출을 명시적 배열 스택으로 옮기면 깊이 제한이 사라집니다. 다만 방문 표시 시점(넣을 때 vs 꺼낼 때)에 따라 중복이 생길 수 있으니 BFS와 같은 기준으로 맞춥니다.

시각화의 물결 퍼짐 = 최단 거리 성질을 이해한 뒤, 섬 세기(DFS) → 격자 최단 거리(BFS) → 다중 시작점 → 상태 그래프 BFS(단어 사다리류) 순으로. 이 유형은 중급의 관문입니다.