백준 / 그래프 / 16928번 / 뱀과 사다리 게임 / JS

문제 간단설명

 

1. 게임의 규칙
   • 1번 칸에서 시작하여 100번 칸에 도달하는 것을 목표로 하는 게임.
   • 플레이어는 매턴 주사위를 굴려 1에서 6까지의 값을 얻어 앞으로 이동.
   • 특정 칸에는 사다리나 뱀이 있음:
     • 사다리: 해당 칸에 도달하면 더 높은 칸으로 이동.
     • 뱀: 해당 칸에 도달하면 더 낮은 칸으로 이동.
2. 입력
   • 첫 줄: 사다리의 수 N과 뱀의 수 M.
   • 다음 N줄: 각 줄에 사다리의 시작과 끝 x,y (항상 x<y).
   • 다음 M줄: 각 줄에 뱀의 머리와 꼬리 u,v(항상 u>v).
3. 출력
   • 1번 칸에서 시작하여 100번 칸에 도달하기 위한 최소 이동 횟수.

 

 

제한 사항

 

• 1≤N,M≤15: 사다리와 뱀의 개수.
• 칸 번호는 1≤x,y,u,v≤1001 \leq x, y, u, v \leq 1001≤x,y,u,v≤100.
• 칸은 서로 연결되며, 순환이 없음(사다리나 뱀을 따라 무한 루프에 빠지지 않음).

 

 

실패 코드 (DP)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

let index = 0;
const [N, M] = input[index++].split(' ').map(Number);
const ladderInfoList = input
  .slice(index, index + N)
  .map((info) => info.split(' ').map(Number));
index += N;
const snakeInfoList = input
  .slice(-M)
  .map((info) => info.split(' ').map(Number));

const MAX = 100;
const NORMAL = 'NORMAL';
const LADDER = 'LADDER';
const SNAKE = 'SNAKE';

const board = Array.from({ length: MAX + 1 }, () => ({
  state: NORMAL,
  count: Infinity,
  next: 0,
}));

function solution() {
  initBoard();
  dp();

  console.log(board[100].count);
}

function initBoard() {
  ladderInfoList.forEach(
    ([x, y]) => (board[x] = { state: LADDER, count: Infinity, next: y })
  );
  snakeInfoList.forEach(
    ([u, v]) => (board[u] = { state: SNAKE, count: Infinity, next: v })
  );

  board[1].count = 0;

  for (let i = 2; i <= 7; i++) {
    const { state, next } = board[i];

    // 2~7까지는 한 번 굴려서 갈 수 있다.
    board[i].count = 1;

    // 만약 사다리가 설치되어있다면, 도착지점도 한 번으로 카운팅한다.
    if (state === LADDER) {
      board[next].count = 1;
    }
  }
}

function dp() {
  for (let i = 7; i <= 100; i++) {
    const { state: curState, next: curNext } = board[i];

    for (let j = i - 6; j < i; j++) {
      const { state: prevState, count: prevCount } = board[j];

      // 전의 칸에 아무것도 설치되어 있지 않을 경우,
      if (prevState === NORMAL) {
        board[i].count = Math.min(board[i].count, prevCount + 1);
      }
    }

    // 사다리가 설치되어 있는 경우,
    if (curState === LADDER) {
      board[curNext].count = board[i].count;
      // 뱀이 있는 경우,
    } else if (curState === SNAKE) {
      board[curNext].count = Math.min(board[curNext].count, board[i].count);
    }
  }
}

solution();

 

dp를 이용해서 문제를 풀었다. 다만, 여느 dp와 달리 '사다리'와 '뱀'이라는 조건에 따라 이동하게 되는 칸이 달라지기 때문에 구조가 약간 복잡하게 되었다. 하지만 테스트케이스는 다 맞았기 때문에 맞을 수 있을줄 알았다.

 

틀린 이유는 논리의 특정성에 있다.

위에서도 말했다시피, 특정 조건에 따라 이동하게 되는 칸이 달라지고 그에 따라 dp의 값이 달라지게 된다.

그 칸에 '사다리'나 '뱀'이 있다면 반드시 이동해야 하므로, 재귀적으로 확인해야 할 필요가 있다는 말이다.

그러므로, "전에 나왔던 dp값에 대해서 현재 값을 특정할 수 없다" 라는 전제때문에 결국 dp로 값을 구할 수가 없다.

 

dp는 이동이 단순히 i -> i+1 식으로 연결되는 단순한 이동에 적합하고, 이 문제는 최단 경로를 구하기 때문에 BFS가 더 적합한 풀이이다.

 

성공 코드 (BFS)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

let index = 0;
const [N, M] = input[index++].split(' ').map(Number);
const ladderInfoList = input
  .slice(index, index + N)
  .map((info) => info.split(' ').map(Number));
const snakeInfoList = input
  .slice(-M)
  .map((info) => info.split(' ').map(Number));

const MAX = 100;
const board = Array.from({ length: MAX + 1 }, () => 0);

function solution() {
  initBoard();
  const minMoveCount = getMinMoveCount();

  console.log(minMoveCount);
}

function initBoard() {
  ladderInfoList.forEach(([x, y]) => (board[x] = y));
  snakeInfoList.forEach(([u, v]) => (board[u] = v));
}

function getMinMoveCount() {
  // [현재 위치, 이동 횟수]
  const queue = [[1, 0]];
  const visited = Array.from({ length: MAX + 1 }, () => false);

  visited[1] = true;

  while (queue.length > 0) {
    const [curNumber, curMoveCount] = queue.shift();

    if (curNumber === MAX) {
      return curMoveCount;
    }

    for (let dice = 1; dice <= 6; dice++) {
      let nextNumber = curNumber + dice;

      if (nextNumber > 100) {
        break;
      }

      // 만약 사다리나 뱀이 설치된 곳이라면,
      // 그것을 이용해서 갈 수 있는 다음칸으로 값을 갱신한다.
      if (board[nextNumber] !== 0) {
        nextNumber = board[nextNumber];
      }

      if (visited[nextNumber]) {
        continue;
      }

      visited[nextNumber] = true;
      queue.push([nextNumber, curMoveCount + 1]);
    }
  }
}

solution();

 

단순한 BFS로직을 이용했다. 단 한가지 추가된점이 있다면, BFS 내부에서 '사다리'나 '뱀'인 칸일 경우 그것을 이용해서 갈 수 있는 다음칸으로 값을 갱신한다는 것이다.