백준 13549 JS 풀이

구하는 값

수빈이가 동생을 찾는 가장 빠른 방법

핵심 아이디어

수빈 이동 경로 -1, 1, 2 3가지 인데 주의점이 2 는 시간 카운팅이 없다는 것이다. 이거를 놓쳐서 계속 틀렸다.

코드

const input= require('fs').readFileSync('dev/stdin').toString().trim().split('\n')

class Que {
    q = [];
    h = 0;
    t = 0;
    push(v) {
        this.q[this.t++] = v;
    }
    shift() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    length() {
        return this.t - this.h;
    }
}

const [n, k] = input[0].split(" ").map(Number);

const visited = new Set();

const que = new Que();
que.push([n, 0]);
visited.add(n);

while (que.length()) {
    const [cur, dep] = que.shift();

    if (cur === k) {
        console.log(dep);
        break;
    }

    for (const d of [2, -1, 1]) {
        if (d !== 2) {
            const next = cur + d;
            // if (next < 0 || next > 100000) continue;
            if (!visited.has(next)) {
                que.push([next, dep + 1]);
                visited.add(next);
            }
        } else {
            const next = cur * d;
            // if (next < 0 || next > 100000) continue;
            if (!visited.has(next)) {
                que.push([next, dep]);
                visited.add(next);
            }
        }
    }
}

헤맨 이유가 크게 2가지가 있다..

1. 수빈 이동 경로 -1, 1, 2 3가지 인데 주의점이 2 는 시간 카운팅이 없다는 것이다.

   따라서 dfs를 돌던 bfs를 돌던 최소시간을 위해서는 *2의 경우를 우선적으로 봐야한다. for문을 돌더라고 2일때를 먼저 봐야한다는 것이다. 이거를 놓쳐서 계속 틀렸다가 반례를 찾아보고 고쳤다

   반례 1 2 ⇒ 0

2. 메모리 초과가 나오면 일단 방문처리와 범위제한을 제대로 했는지보자…

   1. que안에 넣으면서 visited.add를 안해주는 실수를해서 메모리가 터졌었다..
   2. next가 범위를넘어가면 그 뒤에는 알아볼 필요가 없다 이거 안해주니깐 메모리가 터졌었다…

cf) array보다 que로 나타내는게 훨씬 빠르다 아마도 arr.shift()때문일듯

다른사람 코드

// dfs로 풀기

let [A, B] = require("fs").readFileSync("/dev/stdin").toString().split(" ").map(Number);
let result = Infinity;

if (A == 0) {
    jump(1, B, 1);
} else {
    jump(A, B, 0);
}
console.log(result);

function jump(a, b, time) {
    if (b <= a) {
        if (result > time + a - b) {
            result = time + a - b;
        }
        return;
    } else {
        if (b % 2 == 0) {
            jump(a, b / 2, time);
            jump(a, a, time + b - a);
        } else {
            jump(a, b - 1, time + 1);
            jump(a, b + 1, time + 1);
        }
    }
}

DFS로 풀었넹..?