숨바꼭질

문제

언어

  • JavaScript

순서도

  1. BFS 탐색

문제 풀이 step 1

  • 수빈이의 위치가 X 일 때 1 초마다 (X - 1), (X + 1), (2 * X) 이렇게 3 가지 방향으로 움직일 수 있습니다.
  • 이 때, 동생의 위치 K 에 도달하게 되는 시간을 구해야 합니다.
  • 이 문제는 단순 BFS 탐색으로 풀 수 있습니다.
    • 왜냐하면,
    • 우선 0 ~ 100000 은 그래프의 노드가 0 ~ 100000 까지 있다는 것을 암시합니다.
    • 수빈이가 3 가지 방향으로 움직일 수 있다는 것은 현재 수빈이의 위치에서 연결된 노드가 3 가지 방향으로 연결되어 있다는 것을 암시합니다.
    • 그리고 BFS 는 한 단계씩 점진적으로 나아가며 탐색을 합니다.
    • 그래서 BFS 탐색을 하며 1 초 마다 갈 수 있는 방향으로 이동하고, 이동한 위치에 동생이 있는지 판별하면 되겠습니다.
  • 저는 BFS 탐색 과정 중에서 새로운 노드를 방문했을 때, 방문 시점의 초 (seconds) 를 기록함으로써 방문처리를 대신했습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	isEmpty() {
		return this.front === this.rear;
	}

	enqueue(data) {
		this.bucket[++this.front] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.bucket[++this.rear];
	}
}

const isPossibleRoute = (to) => 0 <= to && to <= 100000;

const BFS = (start, end) => {
	const queue = new Queue();
	const seconds = Array.from({length: 100001}, () => -1);

	seconds[start] = 0;
	queue.enqueue(start);

	while (!queue.isEmpty() || seconds[end] === -1) {
		const from = queue.dequeue();

		for (let i = 0; i < 3; i++) {
			let to = null;
			if (i === 0) to = from - 1;
			if (i === 1) to = from + 1;
			if (i === 2) to = from * 2;

			if (!isPossibleRoute(to) || seconds[to] !== -1) continue;

			// 방문 처리 대신 초 (seconds) 기록
			seconds[to] = seconds[from] + 1;
			queue.enqueue(to);
		}
	}

	return seconds[end];
};

const solution = (input) => {
	const [n, k] = input[0].split(" ").map(Number);

	return BFS(n, k);
};

console.log(solution(input));