Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

자바스크립트로 미로 끝 경로 찾기: BFS(너비 우선 탐색)로 도달 가능 여부 판별하기

문제 정의

이번 포스트에서는 N×N 크기의 2차원 배열(미로)이 주어졌을 때, 시작 지점 [0, 0]에서 출구 [N-1, N-1]까지 이동할 수 있는지 판별하는 자바스크립트 함수를 작성해 보겠습니다.

미로의 규칙은 다음과 같습니다.

  • 벽은 문자 'W'(Wall)로 표시되고, 지나갈 수 있는 빈 칸은 '_'로 표시됩니다.
  • 상·하·좌·우 네 방향으로 자유롭게 이동할 수 있습니다.
  • 출구에 도달할 수 있으면 true, 그렇지 않으면 false를 반환해야 합니다.

접근 방법: 너비 우선 탐색(BFS)

격자(grid) 형태의 미로에서 도달 가능 여부를 확인하는 문제에는 너비 우선 탐색(BFS, Breadth-First Search)이 가장 적합합니다. BFS는 큐(queue)를 활용해 시작 지점에서 가까운 칸부터 차례대로 확장해 나가기 때문에, 출구에 닿을 수 있는지를 효율적으로 판별할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

  1. 시작 지점 [0, 0]을 큐에 넣고 탐색을 시작합니다.
  2. 큐에서 칸을 하나 꺼낼 때마다 상하좌우 인접 칸 중 아직 방문하지 않은 빈 칸('_')을 큐에 추가합니다.
  3. 큐에 추가된 칸은 '#'으로 방문 표시하여 같은 칸을 중복 처리하지 않도록 합니다.
  4. 큐가 비면 탐색을 종료하고, 출구 칸이 '#'으로 표시되어 있는지 확인합니다.

코드 구현

const maze = [
  ['_', 'W', 'W', 'W'],
  ['_', 'W', 'W', 'W'],
  ['W', '_', '_', 'W'],
  ['W', 'W', 'W', '_']
];

const canFindPath = (m = []) => {
  const h = m.length;          // 미로의 세로 길이
  const w = m[0].length;       // 미로의 가로 길이
  const queue = [[0, 0]];      // 탐색 대상 좌표를 담는 큐

  // 현재 칸 기준으로 상하좌우(+자기 자신)의 빈 칸을 찾아 큐에 추가
  const mark = (xx, yy) => {
    [[1, 0], [-1, 0], [0, 1], [0, -1], [0, 0]].forEach(([dx, dy]) => {
      const x = xx + dx;
      const y = yy + dy;
      if (x >= 0 && x < w && y >= 0 && y < h && m[y][x] === '_') {
        m[y][x] = '#';         // 방문 표시
        queue.push([x, y]);    // 다음 탐색 대상으로 등록
      }
    });
  };

  do {
    mark(...queue.shift());    // 큐에서 하나씩 꺼내며 탐색 영역 확장
  } while (queue.length);

  // 출구가 방문 처리되었다면 경로가 존재
  return m[h - 1][w - 1] === '#';
};

console.log(canFindPath(maze));

코드 동작 원리

위 코드의 흐름을 단계별로 살펴보면 다음과 같습니다.

  1. 경계 검사: x >= 0 && x < w && y >= 0 && y < h 조건으로 배열 범위를 벗어나는 접근을 사전에 차단합니다.
  2. 방문 표시: 한 번 큐에 들어간 칸은 '#'으로 바뀌기 때문에, 같은 칸이 중복해서 큐에 쌓이는 일이 없습니다.
  3. BFS 반복: do...while 루프가 큐가 빌 때까지 칸을 꺼내고 인접 칸을 추가하며 미로 전체를 탐색합니다.
  4. 결과 판정: 탐색 종료 후 m[h-1][w-1]이 '#'이라면 시작점에서 출구까지 이어지는 경로가 존재한다는 의미입니다.

실행 결과

false

예제 미로에서는 시작 지점 근처의 통로가 벽('W')으로 막혀 있어 출구에 도달할 수 없으므로 false가 출력됩니다.

반대로 경로가 존재하는 미로라면 true가 반환됩니다. 예를 들어 다음 미로를 입력해 보세요.

const openMaze = [
  ['_', '_', 'W', 'W'],
  ['W', '_', '_', 'W'],
  ['W', 'W', '_', 'W'],
  ['W', 'W', '_', '_']
];

console.log(canFindPath(openMaze)); // true

이 미로는 왼쪽 위에서 오른쪽 아래까지 이어지는 통로가 있으므로 true가 출력됩니다.

마무리

이처럼 BFS와 방문 표시 기법만 활용하면 복잡한 자료구조 없이도 미로 경로의 존재 여부를 간단히 판별할 수 있습니다. 모든 칸을 최대 한 번씩만 방문하므로 시간 복잡도는 O(N²)입니다. 미로 게임, 로봇 경로 탐색 등 다양한 분야에 응용할 수 있는 핵심 기법이니 꼭 익혀 두시기 바랍니다.