[백준] 1697번 숨바꼭질 _ Node.js

문제

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

1697번: 숨바꼭질

---

문제 풀이

 이 문제는 1초씩 움직이며 동생에게 도착하는 최소 시간을 구하는 문제이므로 BFS를 사용해보았다. 수빈이는 1초마다 +1 , -1 , X2로 세가지 방법으로 움직일 수 있다. 이 때 위치는 0 <= Point <= 100,000임을 참고하여 범위를 초과하면 queue에 넣지 않는다.

 더해서 visit 배열에 방문한 점은 표시를 하여 중복으로 수행하는 것을 방지한다.

 

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`5 17`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();


function solution(){
    const [N, K] = input().split(" ").map(Number);
    const visit = Array.from({ length: 100100 }, () => 0);

    function bfs(N) {
        const queue = [];
        queue.push([N, 0]);
        visit[N] = 1;
        while (queue.length) {
        const [cur, time] = queue.shift();
        if (cur === K) return time;
        for (next of [cur - 1, cur + 1, cur * 2]) {
            if (!visit[next] && next >= 0 && next <= 100000) {
            visit[next] = 1;
            queue.push([next, time + 1]);
            }
        }
        }
    }
    console.log(bfs(N));

}

solution();