[백준] 숨바꼭질(1697) Javascript

문제 보기

🔒 문제

🔐 해결 과정

1. 수빈이가 이동할 수 있는 세 가지 조건을 이용한 BFS를 수행한다.
2. visited 배열을 만들어서 다음 이동 좌표를 구했을 때 이전에 방문했던 좌표라면 건너뛰도록 한다. (똑같은 방식으로 다음 이동 좌표를 구하기 때문)
3. 다음 이동 좌표가 범위 내에 있고, 방문하지 않은 곳이면 큐에 넣어준다.
4. 수빈과 동생이 만나면 값을 리턴한다.

🔓 풀이 (1h)

1차 시도

let [subin, sis] = require('fs')
    .readFileSync('/dev/stdin')
    .toString()
    .trim()
    .split(' ')
    .map((x) => Number(x));

let cnt = 0;
function bfs() {
    let queue = [subin];
    while (queue.length) {
        let len = queue.length;
        for (let i = 0; i < len; i++) {
            let curr = queue.shift();
            if (curr === sis) return cnt;
            let dics = [curr - 1, curr + 1, curr * 2];
            for (let j = 0; j < 3; j++) {
                if (dics[j] === sis) return cnt + 1;
                if ((dics[j] < 0 || dics[j] > 100000)) continue;
                queue.push(dics[j]);
            }
        }
        cnt++;
    }
}

console.log(bfs());

1초동안 이동할 수 있는 경우의 수를 모두 탐색한 후에 1초씩 올려주는 방식으로 코드를 짰는데 예제는 맞았지만 제출에서 시간초과가 떴다. 생각해보니 visited를 적용하는게 속도를 더 높일 수 있을 것 같았고, 저 첫번째 for문이 불필요한 시간을 잡아먹는 것 같았다.

2차 시도

let [subin, sis] = require('fs')
    .readFileSync('/dev/stdin')
    .toString()
    .trim()
    .split(' ')
    .map((x) => Number(x));

let visited = Array(100001).fill(0);
let cnt = 0;
function bfs() {
    let queue = [[subin, 0]];
    visited[subin] = 1;
    while (queue.length) {
        let [cur, time] = queue.shift();
        if (cur === sis) return time;
        for (next of [cur - 1, cur + 1, cur * 2]) {
            if (!visited[next] && next >= 0 && next <= 100000) {
                visited[next] = 1;
                queue.push([next, time + 1]);
            }
        }
    }
}

console.log(bfs());

시간을 카운트하는 방식을 조금 바꿔서 한 좌표에 대해 소요시간을 1초씩 누적하는 것으로 하고 visited로 방문한 노드를 건너뛰게 했다. 이렇게 하니 성공이 됐다..

🔁 feedback

BFS에서 이동거리나 이동시간을 누적시켜야 할 땐, 한 좌표마다 카운트를 증가시킬 수 있도록 코드를 작성하자. 로직이 훨씬 간단해진다.