N 시작 K 도착
X-1, X+1 1초 / 2*X 0초 / BFS 활용
1. bfs를 활용할 것이기 때문에 queue를 생성
2. [현재위치, 시간]으로 시간을 누적하며 bfs로 정답 도출
3. X가 동생의 위치 K와 같을 경우 정답 출력 후 리턴
4. 2 * X 즉 순간이동 했을 경우 시간 증가 없이 다시 queue에 넣기
5. X - 1, X + 1 즉 걸어서 이동할 경우 시간을 1 증가시켜 queue에 넣기
const [N, K] = require("fs").readFileSync("./dev/stdin").toString().trim().split(" ").map(Number);
const visited = new Array(100001).fill(0);
function bfs(N, K) {
const queue = [];
queue.push([N, 0]);
visited[N] = 1;
while (queue.length) {
let [X, time] = queue.shift();
if (X === K) {
console.log(time);
return;
}
for (const position of [2 * X, X - 1, X + 1]) {
if (!visited[position] && position >= 0 && position <= 100000) {
visited[position] = 1;
if (position === 2 * X) {
queue.push([position, time]);
} else {
queue.push([position, time + 1]);
}
}
}
}
}
bfs(N, K);
2 * X, X - 1, X + 1의 순서를 바꿀 경우 오답 처리 된다 (이것 때문에 오답 파티) 최소 시간을 구해야하기 때문에 시간 증가가 없는 2 * X가 제일 먼저 오는 것 까지는 이해가 됐지만, X - 1, X + 1의 순서는 무슨 연관이 있는지 모르겠다
최소, 최단을 구할 땐 visited를 만들어 갔던 위치에 다시 가지 못하게 해야 시간초과가 나지 않고 문제가 풀림