[BOJ] 2178: 미로 탐색 / JS

문제: https://www.acmicpc.net/problem/2178

 

 

 

 

const [nm, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [n, m] = nm.split(' ').map(Number);
const maze = input.map((s) => s.trim().split('').map(Number));

const visit = new Array(n);
for (let i = 0; i < n; i++) visit[i] = Array.from({ length: m }, () => 0);

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

function isRange(x, y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

function isVisit(x, y) {
  return visit[x][y];
}

function solution() {
  const queue = [[0, 0, 1]];
  while (queue.length) {
    const [x, y, d] = queue.shift();
    if (x + 1 === n && y + 1 === m) {
      console.log(d);
      break;
    }
    for (let k = 0; k < 4; k++) {
      const nx = x + dx[k];
      const ny = y + dy[k];
      if (!isRange(nx, ny) || isVisit(nx, ny) || maze[nx][ny] === 0) continue;
      visit[nx][ny] = 1;
      queue.push([nx, ny, d + 1]);
    }
  }
}
solution();

시작 지점의 거리를 1로 설정하고 이웃한 올바른 길로 갈 때마다 거리에 1씩 더하면 (N, M)까지의 최단거리를 구할 수 있다.

이번 문제는 미로에서 올바른 길을 따라가 최종 도착지까지의 최단 거리를 구하는 문제다.

주어진 입력에서 이웃한 1을 순회해야 하므로 BFS로 풀 수 있다.

 

solution 함수는 도착지점까지의 최단 거리를 구하는 함수다.

주어진 입력에서 1을 찾아 순회하면 되기 때문에 단순 BFS 알고리즘을 작성하면 된다.

 

항상 시작점은 (1, 1)이기 때문에 queue에 [0, 0, 1]을 넣은 채로 시작한다.

여기서 뒤에 넣은 1은 시작점으로부터의 거리를 의미한다.

이웃한 칸으로 이동할 때마다 이 값에 1을 더해서 최종 목적지까지의 최단 거리를 구할 수 있다.

 

다음은 상하좌우 옆칸을 조회하는 코드를 작성해야 한다.

queue에서 front를 pop해서 x, y, d라는 변수에 각 값을 대입한다.

우리는 (N, M)까지의 최단 거리를 구하는 게 목적이기 때문에 x와 y가 도착점의 위치이면 d를 출력하고 함수를 종료하면 된다.

 

x, y가 도착점의 위치가 아니라면 dx, dy 배열에 미리 넣어둔 값으로 상하좌우 칸들에 대한 위치값을 구하고,

해당 요소들에 대한 유효성 검사를 한다.

  => 올바른 범위, 방문X, 올바른 길(값이 1인 것)인지 확인

 

유효성 검사를 통과하면 visit 배열에 방문했다고 표시를 하고, queue에 push하면 된다.

이때 maze[nx][ny]는 현재 칸에 바로 이웃한 칸이므로 d의 값을 1증가시켜서 push 해야한다.

 

위 코드를 작성하고 solution 함수를 호출하면 원하는 값을 얻을 수 있다.