[JavaScript/BFS] 백준 골드 4 : 13913 - 숨바꼭질 4

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

13913번: 숨바꼭질 4

---

📌 작성한 코드 

// 13913
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, `${start}`]);
    visited[start] = true;

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

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

const [time, route] = bfs(N);
console.log(time);
console.log(route);

 

📌 풀이

bfs를 사용해서 N -> F까지 도달하는 최단 거리를 구하고, 최단 거리일 때의 경로를 구하면 되는 문제이다. 

숨바꼭질1 문제에서 경로만 추가하면 되는 문제라 골드 4치고 매우 간단하게 풀 수 있는 문제이다.

https://youme016.tistory.com/227

[JavaScript/BFS] 백준 실버 1 : 1697 - 숨바꼭질

 

bfs를 작성할 때 현재까지 걸린 거리와, 현재 좌표를 큐에 저장하며 한 단계씩 연산을 수행하는 형태로 진행되는데 이때 경로도 함께 저장해주면 된다. 이때 경로를 문자열로 저장하는 것이 포인트이다. 배열에 저장하게 되면 배열을 계속해서 새로 생성해야 하기 때문에 메모리 초과가 발생한다. 문자열에 저장하고 해당 문자열 루트를 그대로 출력해주면 되기 때문에 간편하다.

if (position * 2 < max && !visited[position * 2]) {
            queue.push([position * 2, time + 1, route + ` ${position * 2}`]); // 경로 저장
            visited[position * 2] = true;
        }
        if (position - 1 >= 0 && !visited[position - 1]) {
            queue.push([position - 1, time + 1, route + ` ${position - 1}`]);
            visited[position - 1] = true;
        }
        if (position + 1 < max && !visited[position + 1]) {
            queue.push([position + 1, time + 1, route + ` ${position + 1}`]);
            visited[position + 1] = true;
        }

 

✅ 성공