KimMinJun
Coding Note
KimMinJun
전체 방문자
오늘
어제
  • 분류 전체보기 (487)
    • ALGORITHM (11)
      • 정렬 (6)
      • 최단경로 (1)
      • 자료구조 (1)
      • 슬라이딩 윈도우 (1)
      • etc (2)
    • Git (5)
    • Web (24)
      • Vanilla JS (13)
      • TS (2)
      • React (7)
      • ETC (1)
    • React 공식문서 (번역, 공부) (11)
      • Quick Start (2)
      • Installation (0)
      • Describing the UI (9)
      • Adding Interactivity (0)
      • Managing State (0)
      • Escape Hatches (0)
    • Next.js 공식문서 (번역, 공부) (3)
      • Getting Started (2)
      • Building Your Application (1)
    • PS (432)
      • 백준 (187)
      • Programmers (105)
      • CodeUp (21)
      • STL (3)
      • 제코베 JS 100제 (50)
      • SWEA (0)
      • LeetCode (65)
    • IT (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 관리

공지사항

인기 글

태그

  • Level 1
  • codeup
  • string
  • 수학
  • 제코베 JS 100제
  • programmers
  • LeetCode
  • Level 2
  • js
  • tree
  • Level1
  • C
  • 백준
  • recursion
  • 그래프
  • 다이나믹 프로그래밍
  • C++
  • 문자열
  • Level 0
  • 정렬

최근 댓글

최근 글

hELLO · Designed By 정상우.
KimMinJun

Coding Note

PS/백준

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

2024. 12. 25. 19:06

문제 간단설명

 

  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 내부에서 '사다리'나 '뱀'인 칸일 경우 그것을 이용해서 갈 수 있는 다음칸으로 값을 갱신한다는 것이다.

저작자표시 (새창열림)

'PS > 백준' 카테고리의 다른 글

백준 / 그래프 / 2206번 / 벽 부수고 이동하기 / JS  (0) 2025.01.11
백준 / 그래프 / 9019번 / DSLR / JS  (0) 2025.01.02
백준 / 구현 / 18111번 / 마인크래프트 / JS  (0) 2024.12.21
백준 / 문자열 / 5525번 / IOIOI / JS  (0) 2024.11.09
    'PS/백준' 카테고리의 다른 글
    • 백준 / 그래프 / 2206번 / 벽 부수고 이동하기 / JS
    • 백준 / 그래프 / 9019번 / DSLR / JS
    • 백준 / 구현 / 18111번 / 마인크래프트 / JS
    • 백준 / 문자열 / 5525번 / IOIOI / JS
    KimMinJun
    KimMinJun

    티스토리툴바