[백준][Node.js] 1697번 : 숨바꼭질

 

 

Algorithm

-  숨바꼭질 -

 

---

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0≤N≤100,000)에 있고, 동생은 점 K(0≤K≤100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입출력 예시

 

문제 풀기

const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input;
let queue = [];
let visited = [];
rl.on("line", function (line) {
	input = line
		.toString()
		.split(" ")
		.map((el) => Number(el));
}).on("close", function () {
	visited = Array(100001).fill(false);
	queue = [[input[0], 0]];
	let index = 0;
	while (true) {
		if (!queue[index]) break;
		let [location, count] = queue[index++];
		if (visited[location]) continue;

		visited[location] = true;
		if (location === input[1]) {
			console.log(count);
			break;
		}

		if (location + 1 <= 100000) queue.push([location + 1, count + 1]);
		if (location - 1 >= 0) queue.push([location - 1, count + 1]);
		if (location * 2 <= 100000) queue.push([location * 2, count + 1]);
	}

	process.exit();
});