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

문제 번호

16928번: 뱀과 사다리 게임

 

 

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

문제 풀이

  BFS를 사용하면 간단하게 풀 수 있는 문제이다. 

뱀이나 사다리를 만나면 주사위를 굴리는 횟수를 증가시키지않고 연결된 칸으로 이동한다는점에 주의해서 문제를 풀면된다.

 시작칸은 '1' 이므로 1에서부터 시작하여 1,2,3,4,5,6 을 증가시키면서 BFS를 통하여 탐색을 진행한다. board 라는 배열을 사용하여 문제에서 주어진 사다리와 뱀을 입력받을건데 board의 내용물은 '해당칸에 도착하면 어디로 가야하는지'이다.

board[5] = 5 라면 5번째 칸에 도착했을때는 사다리, 뱀이 연결되어있지 않아서 5번 칸에 그대로 있으면 되고, board[5] = 98 이라면 5번칸은 98번칸과 사다리로 연결되어 있으니 5번칸에 도착하면 사다리를 타고 98번 칸으로 이동하라는 뜻이다.

 그리고 보통의 BFS에서는 visited 배열을 사용하여 '방문여부'를 체크하면서 탐색을 진행한다. 이번 문제에서는 visited 배열에 '방문여부'를 단순히 true || false 로 구분하는것이 아니라 방문한적이 없다면 true 대신 '해당 칸까지 오는데 필요한 주사위 굴림 횟수'를 기록한다. 즉 visited[28] = 4 라면 '28칸까지 오는데 주사위를 4번 굴렸다.' 라는 뜻이 된다. 

 

전체코드

function sol(borad){
  let visited = new Array(101).fill(-1);  // 굴린횟수.

  let q = [];
  q.push(1);  // 시작칸은 1이다.
  visited[1] = 0;

  while(q.length !== 0){
    let cur = q.shift();
    
    for(let dice=1; dice<=6; dice++){
      let next = cur + dice;  // 주사위를 굴려서 나아갈 수 있는 칸의 번호.
      
      if(next > 100)  // 100을 넘어가는 일은 없다.
        continue;    

      next = borad[next]; // 해당칸에 뱀이나 사다리가 있다면 이용해야만 한다.
      if(visited[next] === -1){ // 아직 방문한적 없는 칸.
        visited[next] = visited[cur] + 1;
        q.push(next);
      }  
    }
  }
  console.log(visited[100]);
}

function insert(){
  const input = require('fs').readFileSync('뱀과 사다리 게임/input.txt').toString().trim().split('\n');
  const [n,m] = input[0].split(' ').map(Number);
  
  let board = new Array(101).fill(null).map((_,idx) => idx);  
  
  for(let i=1; i<=n+m; i++){  // 사다리와 뱀.
    let [from,to] = input[i].split(' ').map(Number);
    board[from] = to;
  }  

  sol(board);
}
insert();

특이사항

 BFS를 사용하여 문제를 풀 수 있다는것은 빠르게 캐치하였는데 visited 배열을 주사위 굴린 횟수로 바꾸는것을 생각하지 못해서 오래걸렸다. 정확히 말하면 주사위 굴린횟수 카운트하는 방법을 빠르게 생각하지 못했다.