[백준/JS] 숨바꼭질

문제링크

문제풀이

문제에서 수빈이와 동생이 있는 위치가 숫자로 주어집니다.

일차원 배열에서 BFS를 진행하면 되는 문제입니다.

수빈이가 이동하는 방법

1. x-1
2. x+1
3. x*2

이고 각각 1초씩 걸립니다.

우리는 여기서 수빈이가 동생을 찾기까지 몇 초가 걸리는지를 확인해야 합니다.
-> 이 부분이 좀 헷갈렸습니다. 시간초를 세어주는 변수의 위치를 정확히 어디에 놓아야 할 지 모르겠었기 때문입니다.

bfs는 위와 같이 작동을 합니다. 따라서 queue에 좌표를 넘겨줄 때 시간을 함께 넘겨주면 됩니다.

4 1
6 1
10 1
3 2
8 2
7 2
12 2
9 2
11 2
20 2
2 3
16 3
14 3
13 3
24 3
18 3
22 3
19 3
21 3
40 3
...

위와 같이 다음 좌표 값과 카운트를 함께 찍은 결과 입니다. 그래서 다음좌표로 갈 때마다 카운트를 세주면 저 모든 수를 세어주기 때문에 잘못된 결과가 나오게 됩니다.

결과코드

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

let arr = new Array(100001).fill(0);

let [N, K] = input.shift().split(' ').map(Number);

function bfs(s) {
    let queue = [[s, 0]];
    arr[s] = 1;

    while (queue.length) {
        let [x, cnt] = queue.shift();
        if (x === K) return cnt;

        for (let nx of [x - 1, x + 1, x * 2]) {
            if (nx < 0 || nx > 100000) continue;
            if (arr[nx] === 0) {
                arr[nx] = 1;
                queue.push([nx, cnt + 1]);
            }
        }
    }
}

console.log(bfs(N));