숨바꼭질 3

문제

언어

  • JavaScript

순서도

  1. BFS 탐색

문제 풀이 step 1

  • 백준 1697번 - 숨바꼭질 풀이 에 기원한 문제로 BFS 탐색을 통해서 풀 수 있습니다.
  • 이번에는 수빈이가 순간이동을 할 수 있게 되었습니다. 순간이동을 하면 0 초 후에 2 * X 의 위치로 이동할 수 있게 됩니다.
  • 그래서 BFS 탐색 시 순간이동하는 경우를 다르게 구현해야 합니다.
    • 왜 다르게 구현해야 할까요??
    • BFS 탐색은 한 단계씩 점진적으로 나아가는 방식으로 탐색을 실시합니다.
    • 결론부터 말씀드리면, 현재 노드에서 걷기를 통해서 다음 노드로 가는 단계와 순간이동을 통해서 다음 노드로 가는 단계가 다른 단계이기 때문입니다.
    • 왜냐하면 걷기를 통해서 다음 노드로 가면 1 초가 걸리는데 순간이동을 통해서 다음 노드로 가면 0 초가 걸리기 때문입니다.
    • 즉, 현재 노드에서 순간이동을 통해서 갈 수 있는 모든 노드는 현재 단계와 같은 단계인 것이죠, 반면 걷기를 통해서 갈 수 있는 노드들은 다음 단계인 것입니다.
  • 그렇다면 BFS 탐색의 철학에 맞게 한 단계씩 점진적으로 나아가기 위해서는 순간이동하는 경우를 먼저 탐색하고, 그 다음에 걷는 경우를 탐색하면 되겠습니다.
  • 그리고 노드를 탐색할 때 방문 시점의 초를 기록하는 것으로 방문처리를 대신했습니다.
  • 그리고 동생이 있는 노드를 탐색한 이후의 탐색은 무의미하므로 탐색을 종료합니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 이 방법은 완벽하게 단계가 구분되지 않는데 풀립니다. 제가 생각하기에는 이 문제 한정으로 풀리는 것 같습니다.
  • 걷기를 통해 다음 단계로 가는 경우가 - 1, + 1 이라서 몇몇 중복이 일어나서 가능한 것이라고 생각합니다.
  • 아래에서 알아볼 다른 방법의 풀이가 좀 더 의미가 직관적이고 명확하며, 단계도 확실하게 나뉩니다.

소스 코드 1

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

const MAX = 100001;

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();
	queue.enqueue(n);
	arr[n] = 0;

	while (!queue.isEmpty()) {
		const from = queue.dequeue();
		// 동생을 찾았으면 탐색 종료
		if (from === k) return;

		// 순간 이동
		for (let i = from; 0 < i && i < MAX; i *= 2) {
			if (arr[i] !== -1) continue;
			queue.enqueue(i);
			arr[i] = arr[from];
		}

		// - 1 방향 걷기
		if (from - 1 >= 0 && arr[from - 1] === -1) {
			queue.enqueue(from - 1);
			arr[from - 1] = arr[from] + 1;
		}

		// + 1 방향 걷기
		if (from + 1 < MAX && arr[from + 1] === -1) {
			queue.enqueue(from + 1);
			arr[from + 1] = arr[from] + 1;
		}
	}
};

const solution = (input) => {
	const [n, k] = input[0].split(" ").map(Number);
	const arr = Array.from({length: MAX}, () => -1);

	BFS(n, k, arr);
	return arr[k];
};

console.log(solution(input));

다른 방식의 문제 풀이 step 1

  • 이번 방법은 좀 더 단계를 명확하게 나누기 위해서 queue1, queue2 이렇게 2 개를 준비합니다.
    • 순간이동하는 경우는 queue1 에 넣어줍니다.
    • 걷는 경우는 queue2에 넣어줍니다.
    • 그리고 queue1에 있는 노드들을 모두 탐색했으면 queue2를 탐색하면 됩니다. (저는 옮겨주고 탐색했습니다.)
  • 이렇게 하면 손으로 모든 경우를 그려봤을 때 좀더 명확하게 단계를 구분해서 탐색을 할 수 있습니다.

후기

  • 만약 비슷한 문제가 있다면 이 방식이 더 안전할 것이라고 생각합니다.
  • Queue를 여러개 사용해서 단계를 명확하게 나누고 탐색하는 방법!!

소스 코드 1

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

const MAX = 100001;

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) => {
	let queue1 = new Queue();
	let queue2 = new Queue();
	queue1.enqueue(n);
	arr[n] = 0;

	while (!queue1.isEmpty()) {
		const from = queue1.dequeue();
		if (from === k) return;

		// 1. 순간이동 하는 경우 queue1 에 넣기
		if (from * 2 < MAX && arr[from * 2] === -1) {
			queue1.enqueue(from * 2);
			arr[from * 2] = arr[from];
		}

		// 2. 걷는 경우 queue2에 넣기
		if (from - 1 >= 0 && arr[from - 1] === -1) {
			queue2.enqueue(from - 1);
			arr[from - 1] = arr[from] + 1;
		}

		// 3. 걷는 경우 queue2에 넣기
		if (from + 1 < MAX && arr[from + 1] === -1) {
			queue2.enqueue(from + 1);
			arr[from + 1] = arr[from] + 1;
		}

		// 앞의 단계를 모두 탐색했으면 다음 단계로 넘어간다.
		if (queue1.isEmpty()) {
			queue1 = queue2;
			queue2 = new Queue();
		}
	}
};

const solution = (input) => {
	const [n, k] = input[0].split(" ").map(Number);
	const arr = Array.from({length: MAX}, () => -1);

	BFS(n, k, arr);
	return arr[k];
};

console.log(solution(input));