[JS] 백준 16928번 뱀과 사다리 게임

---

문제 링크

https://www.acmicpc.net/problem/16928

풀이 전략

게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.
도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

코드 

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

const [n, m] = input.shift();

console.log(solution(input));

function solution(arr) {
    const SaL = Array.from({ length: 101 });
    const visited = Array.from({ length: 101 }, () => -1);
    let idx = 0;
    while (idx < n + m) {
        const [x, y] = arr[idx++];
        SaL[x] = y;
    }

    let queue = [];
    queue.push(1);
    visited[1] = 0;

    while (queue.length) {
        const v = queue.shift();
        for (let j = 1; j <= 6; j++) {
            let nv = v + j;

            if (SaL[nv]) nv = SaL[nv];
            if (0 <= nv && nv <= 100 && visited[nv] === -1) {
                visited[nv] = visited[v] + 1;
                queue.push(nv);
            }
        }
    }

    return visited[100];
}

\

회고

범위가 100칸으로 정해져 있고 최솟값을 구하는 문제이기 때문에 bfs로 접근하였다.
주어진 사다리와 뱀을 SaL배열에 넣은 후 만약 sal 배열에 nv인덱스에 값이 존재한다면 그 값을 이용하도록 하였다. 
이 문제도 시간초과와 메모리 초과 때문에 여러가지 단축 방법을 생각해내는 것이 중요하다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)