문제
수빈이가 순간이동을 하거나 걸어서 동생을 찾을 수 있는 최소한의 시간을 구하는 문제이다. 수빈이는 x+1, x-1, 2x의 위치로 이동이 가능하다.
처음에는 이 문제를 완전 탐색으로 풀려고 했다. 각 노드를 가면서 갈 수 있는 모든 경로에 대해 재귀적으로 탐색을 시키면서 최솟값을 계속 갱신하는 방식을 생각했는데, 그렇게 되면 기하급수적으로 함수 호출이 많아지고 콜스택이 수용가능한 정도를 넘어서게 되어 에러가 났다.
결국 알고리즘 분류를 보고 말았는데, bfs를 통해서 문제를 풀어야 한다.
왜 bfs일까?
bfs가 가장 이상적인 풀이법인 이유는 모든 이동이 가중치가 같기 때문에 탐색하는 경로인 x+1, x-1, 2x에 대해서 기존 가중치에 1만 더해주면 된다.
또한, bfs는 현재 횟수를 한 단계씩 확장하면서 탐색하는 방식이고, 해당 단계에서 가능한 모든 경로들을 탐색한 후에 다음 단계로 이동하기 때문에 최단 경로를 보장할 수 있다. 그러므로 여러번 같은 경로를 방문하지 않아도 이전까지 갔다온 시간, 즉 누적 가중치가 최단경로인 셈이다.
풀이
const fs = require("fs");
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, k] = fs
.readFileSync(INPUT_FILE)
.toString()
.trim()
.split(" ")
.map(Number);
const MAX = Math.max(n, k) * 2 + 1;
const visited = new Array(MAX).fill(false);
const queue = [[n, 0]];
visited[n] = true;
while (queue.length) {
const [to, cnt] = queue.shift();
if (to === k) {
console.log(cnt);
break;
}
for (const next of [to + 1, to - 1, to * 2]) {
if (next >= 0 && next < MAX && !visited[next]) {
visited[next] = true;
queue.push([next, cnt + 1]);
}
}
}
배열의 경우는 2x로 순간이동하는 경로까지 생각해야 하므로 넉넉하게 n과 k중 더 큰 값에 2를 곱하고 1을 더해주었다. 또한 다시금 갔던 경로를 재탐색할 필요가 없으므로 방문한 곳을 배열로 관리하여 방문했던 곳의 경우 탐색을 하지 못하도록 했다.
이렇게 bfs 방식으로 x+1, x-1, 2x의 경로에 대해서 탐색을 하고, 목적지인 k에 도달하게 된다면 배열을 나가도록 하였다.
