숨바꼭질 4

문제

언어

  • JavaScript

순서도

  1. 이동 경로를 기록하면서 BFS 탐색
  2. 동생의 위치 K 에서 이동 경로 기록을 이용해서 거꾸로 올라가면서 이동 경로 파악

문제 풀이 step 1

  • 수빈이의 위치가 X 일 때 1 초마다 (X - 1), (X + 1), (2 * X) 이렇게 3 가지 방향으로 움직일 수 있습니다.
  • 이 때, 동생의 위치 K 에 도달하게 되는 시간을 구해야 합니다.
  • 백준 1697번 - 숨바꼭질 풀이 에 이동 경로를 파악하는 로직만 추가하면 됩니다.
  • 이 문제는 단순 BFS 탐색으로 풀 수 있다고 했습니다.
    • 왜냐하면,
    • 우선 0 ~ 100000 까지의 범위는 그래프의 노드가 0 ~ 100000 까지 있다는 것을 암시합니다.
    • 수빈이가 3 가지 방향으로 움직일 수 있다는 것은 현재 수빈이의 위치에서 연결된 노드가 3 가지 방향으로 연결되어 있다는 것을 암시합니다.
    • 그리고 BFS 는 한 단계씩 점진적으로 나아가며 탐색을 합니다.
    • 그래서 BFS 탐색을 하며 1 초 마다 갈 수 있는 방향으로 이동하고, 이동한 위치에 동생이 있는지 판별하면 되겠습니다.
  1. 이동 경로를 기록하면서 BFS 탐색
    • 기존의 BFS 탐색은 방문 처리를 visited 라는 배열을 이용해서 방문했으면 true, 아직 방문하지 않았으면 false 로 처리합니다.
    • 저는 이번 BFS 탐색에서는 어떤 노드를 방문했는지를 기록함으로써 방문처리를 대신했습니다.
    • 왜냐하면, 이렇게 하면 나중에 동생의 위치에서 한 단계씩 거슬러 올라가다가 수빈이의 위치에 도달하면 이동 경로를 파악할 수 있기 때문입니다.
  2. 동생의 위치 K 에서 이동 경로 기록을 이용해서 거꾸로 올라가면서 이동 경로 파악
    • 현재 그래프의 각 노드에 담겨 있는 내용은 이전에 방문한 노드가 기록되어 있습니다.
    • 그래서 동생의 위치 K 에서 수빈이의 위치 X 에 도달할 떄까지 거슬러 올라가면 수빈이의 이동 경로를 파악할 수 있습니다.
  • 파악한 이동 경로는 거꾸로되어 있으므로 뒤집어주고 출력해주면 정답이 됩니다.

후기

  • 수빈이의 위치를 null 로 초기화했습니다.
  • 그리고 마지막에 이동 경로를 파악하는 로직에서 조건을 다음과 정의했습니다.
    • while (arr[index]) {// 거슬러 올라가는 로직}
  • 이렇게하니 이동 경로 상에 arr[index] = 0 인 경로가 있을 경우, 도중에 경로 파악을 멈추게 된다는 것을 알게 되었습니다.
  • 설마라는 생각으로 우선 짜고 돌려봤는 데 역시나 오답이 나왔습니다.
  • 그래서 조건을 다음과 같이 수정했습니다.
    • while(arr[index] !== null) {// 거슬러 올라가는 로직}
  • 이렇게 정답 여부를 판단해주는 플랫폼에서는 이렇게 안일하게 짜도 괜찮겠지만, 만약 정답 여부를 알려주지 않는 플랫폼에서는 수정의 기회가 없었을 것 같습니다.
  • 좀 더 꼼꼼하게 짜야할 필요성을 느꼈습니다.

소스 코드 1

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

const MAX_SIZE = 100001;
const isPossibleRoute = (to) => 0 <= to && to < MAX_SIZE;

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 BFS = (n, k, arr) => {
	const queue = new Queue();
	// 수빈이의 위치는 null 로 초기화
	arr[n] = null;
	queue.enqueue(n);

	while (!queue.isEmpty() || arr[k] === -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) || arr[to] !== -1) continue;

			// 방문하는 노드에 이전 노드를 기록함으로써 이동 경로를 기록하고 방문 처리도 같이 처리
			arr[to] = from;
			queue.enqueue(to);
		}
	}
};

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

	// 1. 이동 경로를 기록하면서 BFS 탐색
	const arr = Array.from({length: MAX_SIZE}, () => -1);
	BFS(n, k, arr);

	// 2. 동생의 위치 K 에서 이동 경로 기록을 이용해서 거꾸로 올라가면서 이동 경로 파악
	const order = [k];
	let index = k;
	// 수빈이의 위치까지 거슬러 올라가며 이동 경로를 파악
	while (arr[index] !== null) {
		order.push(arr[index]);
		index = arr[index];
	}

	return `${order.length - 1}\n${order.reverse().join(" ")}`;
};

console.log(solution(input));