백준 16928: 뱀과 사다리 게임 - javascript(bfs)

문제 출처 

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

 

정답 풀이 

베베 꼬아서 생각했던 문제였는데, 사실 간단하다. 

 

기존에는 최대한 사다리를 타고 가게 하면서, 뱀을 피하면서 ~ 아무것도 해당되지 않을 때는 주사위로 이동하면서 ~~ ...

 

그것이 아니라 

queue에다가 

현재 위치 = 1

주사위 던진 횟수 = 0 

을 먼저 넣는다. 

 

그리고 주사위를 돌리는 거다 !! 

1부터 6까지 ! 

그때의 next position 이 나오는데 

=> 사다리가 잇다면 next position을 사다리로 이동한 결과를 넣어주고 

=> 뱀이 있다면 next position을 내려간 이동 결과를 넣어준다. 

 

이를 위해서 사다리와 뱀 좌표는 map 객체로 관리한다.

 

 이걸 계속하다가 위치가 100이상인 점이 나올 때 그때의 cnt(주사위 던진 횟수) 를 출력하면 된다. 

 

정답 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,m] = input[0].split(' ').map(v => +v); 
let ladder = new Map()
let snake = new Map()
for(let i=1; i<=n; i++){
   let [a,b] = input[i].split(' ').map(v => +v)
    ladder.set(a,b)
}
for(let i=n+1; i<=n+m; i++){
    let [a,b] = input[i].split(' ').map(v => +v)
    snake.set(a,b)
}

const visited = new Array(101).fill(false); 
visited[1] = true; 

const queue = [[1,0]]; 

while(queue.length){
    let [position, cnt] = queue.shift()
    if(position >= 100){
        console.log(cnt)
        return; 
    }
    for(let i=1; i<=6; i++){
        let next = position + i
            
        if(ladder.has(next)){
          next = ladder.get(next)
        }
        if(snake.has(next)){
          next = snake.get(next) 
        }
        
        if(visited[next]) continue; 
        
        visited[next] = true; 
        queue.push([next, cnt+1])
    }
}

console.log(answer)