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

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

12851번: 숨바꼭질 2

---

📌 작성한 코드

// 12851
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 answer = [];

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

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

        if (position === K) {
            answer.push(time);
            continue;
        }

        const calc = [position * 2, position - 1, position + 1];
        for (let i = 0; i < 3; i++) {
            if (calc[i] <= max && calc[i] >= 0 && !visited[calc[i]]) {
                queue.push([calc[i], time + 1]);
            }
        }
    }
};

if (N >= K) {
    console.log(N - K);
    console.log(1);
} else {
    bfs(N);
    const min = Math.min(...answer);
    const count = answer.filter((val) => val === min).length;
    console.log(min);
    console.log(count);
}

 

📌 설명 

bfs를 통해 동생에게 가는 최단 거리와, 최단 거리로 가는 방법의 수를 구하는 문제이다. 

숨바꼭질 1의 문제에서 최단 거리로 가는 방법의 수만 추가로 구하면 되는데, 이 때 주의해야 할 점이 있다.

 

이전의 숨바꼭질 1은 최단 거리만 구하면 됐기에 다음에 접근할 위치를 큐에 넣으면서 방문 처리를 해줬었는데, 여기서는 최단 거리로 가는 방법의 수를 모두 구해야 하니까 그렇게 하면 안된다. 잘 이해가 안갈 수 있지만 예시를 통해 이해해보자. 

 

5에서 17으로 이동한다고 가정해보자. 5에서 17으로 이동하는 방법은 2가지가 존재한다.

(1) 5 → 10 → 9 → 18 → 17

(2) 5 → 4 → 8 → 16 → 17

 

이때 (1)의 상황에서 position = 18, time = 3인 순간에 도착했다고 하자. -1 연산을 통해 우리가 원하던 17에 도달할 수 있게 되었다. 하지만 큐에 넣을 때는 해당 값이 답인지 확인하는 로직은 없기 때문에 그냥 방문 처리 후에 큐에 삽입하게 된다.

queue.push([calc[i], time + 1]); // [17,4]
visited[calc[i]] = true; // 17에 방문처리 해버림

 

그리고 나서 다음 큐의 요소를 꺼내서 계산하려고 한다. (2)의 position = 16, time = 3인 상황인 것이다. 그러나 여기서도 우리는 +1 연산을 통해서 17에 도달할 수 있다. 그러나 이전 연산에서 17에 도달하고나서 방문 처리를 해서 우리는 17에 접근할 수 없게 된다. 해당 포지션을 큐에 삽입 할 수 없는 것이다. 17에 갈  수 있는 최소 거리 방법이 존재함에도 불구하고 그 개수를 셀 수 없게 된다. 

 

이 문제를 해결하기 위해서는 어떻게 해야 할까? 아주 간단하다. 방문 처리를 큐에 넣을 때가 아니라 큐에서 꺼낼 때 해주면 된다.

const [position, time] = queue[idx++];
visited[position] = true;

그러면 (2)번과 같은 상황에서도 17에 도달할 수 있기 때문에 그 개수를 제대로 셀 수 있게 된다. 최단 거리만 구하는 경우에는 갈 수 있는 최단 경로 하나만 구하면 되기 때문에 큐에 넣으면서 방문 처리를 해주어도 문제가 되지 않았지만, 이렇게 개수를 세야하는 경우에는 큐에 넣을 때 방문 처리를 하면 원하는 대로 동작하지 않게 된다.

 

📌 참고

설명하기 어려운 부분은 다른 블로그의 설명을 참고해서 작성해보았다.

https://hibee.tistory.com/181

[BFS] 12851번 숨바꼭질2

 

✅ 성공