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

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

1697번: 숨바꼭질

---

📌 작성한 코드 

// 1697

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

let [N, K] = input.pop().split(" ").map(Number);

const calc = (idx, value) => {
    if (idx === 0) return value + 1;
    if (idx === 1) return value - 1;
    if (idx === 2) return value * 2;
};

const solution = () => {
    const visited = new Array(100001).fill(false);
    const bfs = (start) => {
        const queue = [];
        queue.push([start, 0]);
        visited[start] = true;

        let idx = 0;
        while (queue.length > idx) {
            const [node, time] = queue[idx++];
            for (let i = 0; i < 3; i++) {
                const newNode = calc(i, node);
                if (!visited[newNode] && newNode <= 100000) {
                    visited[newNode] = true;
                    queue.push([newNode, time + 1]);
                }

                if (newNode === K) {
                    return time + 1;
                }
            }
        }
    };
    if (N === K) return 0;
    return bfs(N);
};

console.log(solution());

 

📌 풀이 

- 수빈이의 위치에서 동생의 위치까지 가는 최단 시간(최단 거리)를 구하는 문제 

-> 각 위치에서 할 수 있는 3가지 이동을 하면서 가장 먼저 동생의 위치에 도달하는 방법 찾기 -> bfs 이용해서 최단 거리 구하기

 

✅ (1) 기본 세팅 

- 방문 여부를 저장할 visited 배열 선언

-> 이미 방문한 위치에 또 방문하지 말라는 제한 사항은 없지만, 이미 방문한 위치에 또 가면 똑같은 연산을 반복하므로 필요없음 

- 방문할 위치를 저장할 큐 선언 

- 큐에는 [현재 위치, 걸린 시간]을 삽입해서 저장해줌  

const visited = new Array(100001).fill(false);
    const bfs = (start) => {
        const queue = [];
        queue.push([start, 0]);
        visited[start] = true;
// ...

 

✅ (2) bfs 작동 

- 인덱스 선언 -> 인덱스로 큐에서 이동하지 않고, shift 사용하면 시간 초과 발생 

- 큐에서 꺼내서 이동할 수 있는 3가지 방법(더하기,빼기,곱하기) 연산 

- 연산해서 나온 새로운 위치에 방문한 적이 없고, 해당 위치가 10만을 넘지 않으면 이동하고 큐에 넣기

-> 10만 제한 사항을 넣지 않으면 메모리 초과 발생 

let idx = 0;
while (queue.length > idx) {
    const [node, time] = queue[idx++];
    for (let i = 0; i < 3; i++) {
        const newNode = calc(i, node);
        if (!visited[newNode] && newNode <= 100000) {
            visited[newNode] = true;
            queue.push([newNode, time + 1]);
        }

        if (newNode === K) {
            return time + 1;
        }
    }
}

 

✅ (3) 이동 연산 

- 인덱스와 값을 입력받아서 해당 인덱스에 맞는 연산 진행 

const calc = (idx, value) => {
    if (idx === 0) return value + 1;
    if (idx === 1) return value - 1;
    if (idx === 2) return value * 2;
};

 

📌 주의 

- shift() 사용하면 시간 초과 발생

- 10만 이하 제한 사항 넣지 않으면 메모리 초과 발생

---