https://www.acmicpc.net/problem/12851
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
📌 작성한 코드
// 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에 도달할 수 있기 때문에 그 개수를 제대로 셀 수 있게 된다. 최단 거리만 구하는 경우에는 갈 수 있는 최단 경로 하나만 구하면 되기 때문에 큐에 넣으면서 방문 처리를 해주어도 문제가 되지 않았지만, 이렇게 개수를 세야하는 경우에는 큐에 넣을 때 방문 처리를 하면 원하는 대로 동작하지 않게 된다.
📌 참고
설명하기 어려운 부분은 다른 블로그의 설명을 참고해서 작성해보았다.
[BFS] 12851번 숨바꼭질2
12851_숨바꼭질2 12851번 숨바꼭질 2 https://www.acmicpc.net/problem/12851 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,00
hibee.tistory.com
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/백트래킹] 백준 실버 3 : 15650 - N과 M (2) (0) | 2024.02.01 |
|---|---|
| [JavaScript/백트래킹] 백준 실버 3 : 15649 - N과 M (1) (1) | 2024.02.01 |
| [JavaScript/재귀] 백준 실버 1: 1992 - 쿼드트리 (0) | 2024.01.30 |
| [JavaScript/재귀] 백준 실버 2 : 2630 - 색종이 만들기 (0) | 2024.01.30 |
| [JavaScript/재귀] 백준 실버 2 : 1980 - 종이의 개수 (0) | 2024.01.30 |