PS/백준
백준 / 그래프 / 1697번 / 숨바꼭질 / JS
KimMinJun
2023. 12. 19. 16:33
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');
const [N, K] = input.shift().split(' ').map(Number);
const MAX = 1e5 + 1;
const solution = () => {
bfs();
};
const bfs = () => {
const queue = [[N, 0]];
const visited = Array.from({ length: MAX }, () => false);
visited[N] = true;
while (queue.length > 0) {
const [curPos, curTime] = queue.shift();
if (curPos === K) {
console.log(curTime);
return;
}
// (현재 칸 - 1)로 이동
if (curPos > 0 && !visited[curPos - 1]) {
queue.push([curPos - 1, curTime + 1]);
visited[curPos - 1] = true;
}
// (현재 칸 + 1)로 이동
if (curPos < MAX - 1 && !visited[curPos + 1]) {
queue.push([curPos + 1, curTime + 1]);
visited[curPos + 1] = true;
}
// (현재 칸 * 2)로 이동
if (curPos * 2 < MAX && !visited[curPos * 2]) {
queue.push([curPos * 2, curTime + 1]);
visited[curPos * 2] = true;
}
}
};
solution();