← 16주차 · BFS 최단 거리와 격자 탐색
쉬움BFS그래프

미로 최단 거리

0은 지나갈 수 있는 길, 1은 벽인 격자 grid가 주어져요. 왼쪽 위 칸 (0, 0)에서 오른쪽 아래 칸 (행-1, 열-1)까지 상하좌우로만 움직여요.

출발 칸과 도착 칸을 모두 포함해 지나는 칸 수가 가장 적은 경로의 칸 수를 반환해요. 도착할 수 없으면 -1을 반환해요.

BFS는 시작점에서 가까운 칸부터 층층이 퍼지니, 도착 칸에 처음 닿은 순간이 곧 최단이에요.

예시

예시 1
입력
grid = [[0, 0, 1], [1, 0, 0], [1, 1, 0]]
출력
5
설명
(0,0)→(0,1)→(1,1)→(1,2)→(2,2), 다섯 칸이에요.
예시 2
입력
grid = [[0, 1], [1, 0]]
출력
-1
설명
벽에 막혀 도착 칸으로 갈 수 없어요.

제한 사항

  • 1 ≤ 행, 열 ≤ 1,000
  • 각 칸은 0 또는 1이고, 시작 칸 (0, 0)은 항상 0이에요.
거리 배열을 -1로 채우고 시작 칸을 1로 둬요(칸 수를 세니까요). 큐에서 칸을 꺼내 상하좌우 이웃 중 벽이 아니고 아직 방문하지 않은 칸을 현재 + 1로 표시하며 넣어요. 마지막에 도착 칸의 값을 반환하면 돼요.
javascript
function mazeShortest(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const DX = [-1, 1, 0, 0];
  const DY = [0, 0, -1, 1];
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [[0, 0]];
  let head = 0;
  dist[0][0] = 1;
  while (head < queue.length) {
    const [x, y] = queue[head++];
    for (let d = 0; d < 4; d++) {
      const nx = x + DX[d];
      const ny = y + DY[d];
      if (nx < 0 || ny < 0 || nx >= rows || ny >= cols) continue;
      if (grid[nx][ny] === 1 || dist[nx][ny] !== -1) continue;
      dist[nx][ny] = dist[x][y] + 1;
      queue.push([nx, ny]);
    }
  }
  return dist[rows - 1][cols - 1];
}
이전 문제이분 그래프 판별
다음 문제토마토 익히기
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.