https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
📌 작성한 코드
// 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));
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 실버 2 : 5397 - 키로거 (1) | 2024.01.20 |
|---|---|
| [JavaScript] 백준 실버 3 : 3273 - 두 수의 합 (1) | 2024.01.20 |
| [JavaScript/BFS] 백준 골드 5 : 6593 - 상범 빌딩 (0) | 2024.01.16 |
| [JavaScript/DFS] 백준 실버 1 : 2583 - 영역 구하기 (0) | 2024.01.15 |
| [JavaScript/BFS] 백준 실버 1 : 7562 - 나이트의 이동 (0) | 2024.01.12 |