[JavaScript] 백준 코딩테스트 2178. 실버 1 : 미로 탐색

📌  문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

📌  입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

📌  출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

📌  예제 입출력

---

📌  풀이

구할 것

• 백준 데이터 받기
  • 첫 줄에 가로와 세로가 주어진다. 첫 줄을 제외한 부분이 미로의 구간이다. 이 때 모두 한 줄이 모두 붙어서 나오기 때문에 (101111) 이걸 모두 split으로 쪼개주고 Number로 바꾸어 반환한다. 여기까지 완성하면 가로가 6이고 세로가 4인 그래프가 만들어진다. 이 때 인덱스와 가로, 세로의 길이가 같지 않다는 점을 기억해야 한다. 따라서 실제로 (1, 1)에서 시작하지만 배열 상에서는 인덱스가 [0][0]인 부분부터 시작하는 것이다. >> 첫 줄을 shift()로 받고 가도 된다.
• 기본 구성 만들기
  • 최단 거리를 구하고 있으므로 깊게 들어가는 게 아니라 넓게 넓게 인접한 1을 따라 가야 한다. 빈 배열 queue를 선언한다.
  • 그래프는 특히 템플릿만 익혀도 어느 정도 뼈대가 잡히는 것 같다. 좌표의 경우 인접한 상하좌우를 살펴야 할 때 dx, dy로 이동할 거리를 배열로 만들어둔다. 즉 현재 좌표에서 위로 움직이려면 x좌표는 그대로, y좌표는 1 증가한다. 반대로 아래의 경우에도 x좌표는 그대로, y좌표는 1 감소한다. 이런 식으로 상하좌우를 배열화 하면 dx = [0, 0, -1, 1], dy = [1, -1, 0, 0]이 된다. 이 쌍을 잘 기억하자. >> dir = [[0, 1], [0, -1], [-1, 0], [1, 0]] 으로 묶어서 해도 된다.
  • 방문 여부를 체크할 visited 배열을 생성한다. 크기는 현재 그래프와 동일하게 한다.
• 미로 탐색
  • maze[0][0] = 1로 첫 칸부터 카운트 하고, queue에는 이 좌표인 [0, 0]을 push + 방문처리를 한다.
  •  queue에 값이 없어질 때까지 돌리는데 처음에 넣은 좌표를 [x, y]로 구조 분해 할당해 shift 한다. (일반 bfs와 똑같음)
  • 이후 이 x, y에 dx[i], dy[i]를 더했을 때 그 수가 범위를 벗어나지 않는지 확인한다.
    • 이 값들은 0보다 크거나 같아야 하고 (마지노선) row, col보다는 작아야 한다. 
    • 그렇게 좌표를 구했을 때 값이 1이어야 한다. (0이면 이동 불가)
    • 방문하지 않아야 한다. (=중복 제외)
  • 조건에 해당할 경우에만 queue에 push + 방문처리 후 이 값에 기존 값의 1을 더해준다.
    • 이전 값보다 얼마나 넓게 퍼졌는지 단계를 세주는 것
  • 최종적으로 답을 낼 때는 인덱스를 고려해서 maze[row - 1,][col - 1]를 리턴한다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const [row, col] = input[0].split(" ").map(Number);
const maze = input.slice(1).map((v) => v.split("").map(Number));
const queue = [];

// 상하좌우
const dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];

// 방문 여부를 체크하는 배열
const visited = Array.from(Array(row), () => Array(col).fill(false));

// 시작점 (문제에서는 1, 1)
maze[0][0] = 1;
queue.push([0, 0]);
visited[0][0] = true;

while (queue.length) {
  const [x, y] = queue.shift();

  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];

    if (
      nx >= 0 &&
      ny >= 0 &&
      nx < row &&
      ny < col &&
      maze[nx][ny] === 1 &&
      !visited[nx][ny]
    ) {
      queue.push([nx, ny]);
      visited[nx][ny] = true;
      maze[nx][ny] = maze[x][y] + 1;
    }
  }
}

console.log(maze[row - 1][col - 1]);

 

너무 간단하게 푸신 다른 분 풀이가 있어서 충격 받음.

[JS] 백준 2178번 미로 탐색

[row, col]과 그래프 구성, 좌표 만드는 것까지는 똑같은데 이 분은 구조 분해 할당을 이용해 훨씬 쉽게 푸셨다. 🥹

동일하게 조건에 충족할 경우 [x좌표, y좌표, 거리]를 넣어주시는데 코드도 깔끔해서 많이 배웠다.