[JS] 백준 1697번 숨바꼭질

Contents

• 문제 링크
• 풀이 전략
• 첫번째 코드 

---

문제 링크

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

풀이 전략

 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이는 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 

첫번째 코드 

const fs = require("fs");
const [n, k] = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);

console.log(solution(n, k));

function solution(n, k) {
    const visited = Array.from({ length: 100001 }, () => 0);
    const queue = [];
    visited[n] = 0;
    queue.push([n, 0]);

    while (queue.length) {
        const [v, cnt] = queue.shift();
        if (v === k) return cnt;
        for (const nv of [v - 1, v + 1, v * 2]) {
            if (visited[nv] || nv < 0 || nv > 100000) continue;
            visited[nv] = 1;
            queue.push([nv, cnt + 1]);
        }
    }
}

너무 느리다....

시간,공간 복잡도가 너무 많이 사용되어서 어떻게 줄일까 생각하다가 다른 분들의 코드를 참고하여 다시 작성하였다. 

 

const fs = require("fs");
const [n, k] = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);

console.log(solution(n, k));

function solution(n, k) {
    const visited = Array.from({ length: 100001 }, () => 0);
    let queue = [];
    let cnt = 0;
    visited[n] = 0;
    queue.push(n);

    while (queue.length) {
        const tmp = [];
        for (const v of queue) {
            if (v === k) return cnt;
            for (const nv of [v - 1, v + 1, v * 2]) {
                if (visited[nv] || nv < 0 || nv > 100000) continue;
                visited[nv] = 1;
                tmp.push(nv);
            }
        }
        queue = tmp;
        cnt++;
    }
}

우선 queue안에 cnt변수를 넣는 것을 뺄 수 있었다. 그리고 임시로 생성한 tmp 배열 안에 그 다음 값들을 넣은채 queue에다가 재정의 하면 빠르게 답을 낼 수 있다.

 

회고

답은 잘 낼 수 있었지만 시간초과 때문에 애먹었던 문제였다. input으로 들어오는 값들의 범위를 잘 살펴보아서 처리해주면 쉽게 풀 수 있다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)