[JavaScript/BFS] 백준 골드 5 : 13549 - 숨바꼭질 3

 

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

13549번: 숨바꼭질 3

---

📌 작성한 코드 

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

const [N, K] = input.shift().split(" ").map(Number);
const max = 100001;
const visited = new Array(max).fill(false);

const bfs = (start) => {
    const queue = [];
    queue.push([start, 0]);
    visited[start] = true;

    let idx = 0;
    while (queue.length > idx) {
        const [position, time] = queue[idx++];

        if (position * 2 < max && !visited[position * 2]) {
            queue.push([position * 2, time]);
            visited[position * 2] = true;
        }
        if (position - 1 >= 0 && !visited[position - 1]) {
            queue.push([position - 1, time + 1]);
            visited[position - 1] = true;
        }
        if (position + 1 < max && !visited[position + 1]) {
            queue.push([position + 1, time + 1]);
            visited[position + 1] = true;
        }
        if (position === K) {
            return time;
        }
    }
};

if (N >= K) {
    console.log(N - K);
} else {
    console.log(bfs(N));
}

 

📌 풀이 

bfs를 통해서 N-> K까지 이동하는 최단 시간을 구하는 문제이다. 주의해야 할 점은 *2를 할 때는 순간이동을 하기 때문에 시간이 추가되지 않는 다는 것이다. 

 

1. 방문 배열 초기화하기

N과 K의 범위는 100,000 이하이고, 해당 값 이상의 값에서 -1를 통해 K값에 도달하는 것은 비효율적인 방법이기 때문에방문 가능한 값들의 범위를 10만 +1로 설정해서 visited 배열을 초기화한다. 

 

* 비효율적인 이유에 대해서 더 설명하자면 *2를 통해 범위 이상으로 넘어가서 -1을 반복해서 1씩 줄여나가는 것보다, -1을 먼저 적용하고 해당 값을 *2해서 원하는 값에 도달하는 것이 훨씬 효율적이다. *2 이후에 -2를 한것과 다름없는 결과가 나오기 때문이다.

const max = 100001;
const visited = new Array(max).fill(false);

 

2. bfs 작성하기 

다른 bfs를 작성할 때와 마찬가지로 작성해주면 되는데 특히 주의해야 할 부분이 몇가지 있다.

 

1. *2 할 시에는 시간이 증가하지 않는다는 점 

2. bfs를 통해 큐에서 먼저 들어온 값을 먼저 방문해서 확인하므로 시간이 적게 걸리는 *2를 가장 먼저 수행해야 한다는 점 

3. +1보다 -1 연산을 먼저 하는 것이 더 효율적이기 때문에 -1 연산을 더 먼저 해야 한다는 점

=> 연산의 순서는 *2 -> -1 * +1이다.

 

* 3번의 이유를 예를 들어 설명해보자. N=4, K=6이다.

(1) *2 -> -1 -> +1 

최단 거리 경로 : [4->3->6] , 시간 : 1초 : 빼기를 먼저하기 때문에 *2 -> -1 -> *2 순으로 연산 적용

(2) *2 -> +1 -> -1 

최단 거리 경로 : [4->5->6] , 시간 : 2초 : 더하기를 먼저하기 때문에 *2 -> +1 -> +1 순으로 연산 적용

 

빼기 후 곱하기를 하는 것이 더하기를 여러번 하는 것보다 더 시간이 적게 걸리게 도달할 수 있는 방법이기 떄문에 빼기를 먼저 해야한다.

const bfs = (start) => {
    const queue = [];
    queue.push([start, 0]);
    visited[start] = true;

    let idx = 0;
    while (queue.length > idx) {
        const [position, time] = queue[idx++];

        if (position * 2 < max && !visited[position * 2]) {
            queue.push([position * 2, time]);
            visited[position * 2] = true;
        }
        if (position - 1 >= 0 && !visited[position - 1]) {
            queue.push([position - 1, time + 1]);
            visited[position - 1] = true;
        }
        if (position + 1 < max && !visited[position + 1]) {
            queue.push([position + 1, time + 1]);
            visited[position + 1] = true;
        }
        if (position === K) {
            return time;
        }
    }
};

 

3. 답 출력하기 

N>=K인 경우는 줄일 수 있는 방법이 -1밖에 없기 때문에 bfs없이도 바로 구할 수 있다.

if (N >= K) {
    console.log(N - K);
} else {
    console.log(bfs(N));
}

 

✅ 성공