JS Coding Blog

가장 가까운 충전소까지의 최단 거리

자바스크립트 코딩테스트 문제로 bfs 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium bfs 함수명: solution 제한 시간: 300ms

2차원 격자 grid가 주어집니다. 각 칸은 다음 셋 중 하나입니다.

  • 'C': 충전소
  • 'E': 이동 가능한 빈 칸
  • 'W': 벽

상하좌우로 한 칸씩만 이동할 수 있을 때, 각 이동 가능한 칸에서 가장 가까운 충전소까지의 최단 거리를 2차원 배열로 반환하세요.

  • 충전소 칸의 거리는 0입니다.
  • 벽 칸은 결과에서도 -1로 표시합니다.
  • 어떤 빈 칸이 어느 충전소와도 연결되지 않으면 그 칸도 -1로 표시합니다.
  • 충전소가 하나도 없으면 모든 이동 가능한 칸은 -1입니다.

제한사항

  • 1 <= grid.length <= 200
  • 1 <= grid[i].length <= 200
  • 각 칸의 값은 'C', 'E', 'W' 중 하나입니다.
  • grid는 직사각형 형태입니다.
  • 이동은 상하좌우 네 방향만 가능합니다.
  • 반환 배열의 크기는 입력 grid와 같아야 합니다.

예시

  • 입력: 
    [
  ['E', 'E', 'C'],
  ['W', 'E', 'E'],
  ['E', 'E', 'E']
]

    출력:

    [
  [2, 1, 0],
  [-1, 2, 1],
  [4, 3, 2]
]
  • 입력: 
    [
  ['E', 'W', 'E'],
  ['W', 'W', 'W'],
  ['C', 'E', 'E']
]

    출력:

    [
  [-1, -1, -1],
  [-1, -1, -1],
  [0, 1, 2]
]

힌트

  • 각 빈 칸마다 충전소를 따로 찾으면 너무 느릴 수 있습니다.
  • 한 충전소에서만 시작하지 말고, 모든 충전소에서 동시에 출발한다고 생각해 보세요.
  • BFS는 먼저 도착한 거리가 항상 최단 거리라는 점을 이용할 수 있습니다.

해설

이 문제는 격자에서 최단 거리를 구하는 전형적인 BFS 문제입니다. 다만 각 빈 칸마다 가장 가까운 충전소를 따로 찾으려고 하면 비효율적입니다.

예를 들어 빈 칸이 많고 충전소도 여러 개라면, 각 칸마다 BFS를 다시 돌리는 방식은 시간 초과로 이어질 수 있습니다.

이럴 때는 관점을 뒤집는 것이 핵심입니다.

1. 모든 충전소를 동시에 시작점으로 둡니다

우리가 원하는 것은 “각 칸에서 가장 가까운 충전소까지의 거리”입니다.

이 말은 반대로 보면 “각 충전소에서 퍼져 나가며 처음 도달한 거리”와 같습니다.

그래서 모든 'C' 칸을 큐에 먼저 넣고 거리를 0으로 시작합니다.

2. BFS로 바깥으로 한 겹씩 확장합니다

BFS는 거리 0인 칸들, 거리 1인 칸들, 거리 2인 칸들 순서로 확장됩니다. 따라서 어떤 빈 칸을 처음 방문한 순간의 거리가 그 칸의 최단 거리입니다.

진행 방식은 다음과 같습니다.

  1. 결과 배열을 전부 -1로 초기화합니다.
  2. grid를 순회하면서
    • 'C'는 결과에 0을 기록하고 큐에 넣습니다.
    • 'W'는 그대로 -1로 둡니다.
  3. 큐에서 칸을 하나 꺼내 상하좌우를 봅니다.
  4. 아직 방문하지 않은 'E' 칸이면 현재 거리 + 1을 기록하고 큐에 넣습니다.
  5. BFS가 끝나면 방문되지 않은 'E' 칸은 연결되지 않은 칸이므로 -1 그대로 남습니다.

3. 왜 이 풀이가 맞을까요?

BFS는 항상 더 짧은 거리부터 처리합니다.

여기서는 모든 충전소를 한꺼번에 시작점으로 넣었기 때문에, 어떤 빈 칸에 가장 먼저 도달한 경로는 모든 충전소 중 가장 가까운 충전소에서 온 최단 경로입니다.

즉, 나중에 더 긴 거리로 다시 도착할 가능성은 있어도 더 짧은 거리로 도착할 수는 없습니다. 그래서 첫 방문 때 기록한 값이 정답입니다.

4. 복잡도

  • 격자의 각 칸은 최대 한 번만 큐에 들어갑니다.
  • 시간 복잡도: O(rows * cols)
  • 공간 복잡도: O(rows * cols)

칸마다 BFS를 다시 돌리는 방식보다 훨씬 효율적입니다.

function solution(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => Array(cols).fill(-1));
  const queue = [];
  let head = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 'C') {
        dist[r][c] = 0;
        queue.push([r, c]);
      }
    }
  }

  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  while (head < queue.length) {
    const [r, c] = queue[head++];

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] !== 'E') continue;
      if (dist[nr][nc] !== -1) continue;

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

  return dist;
}

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.