1️⃣ 문제 설명

13549번: 숨바꼭질 3

스크린샷 2022-09-28 오후 11.08.19.png


2️⃣ 풀이

N 시작 K 도착
X-1, X+1 1초 / 2*X 0초 / BFS 활용

1. bfs를 활용할 것이기 때문에 queue를 생성
2. [현재위치, 시간]으로 시간을 누적하며 bfs로 정답 도출
3. X가 동생의 위치 K와 같을 경우 정답 출력 후 리턴
4. 2 * X 즉 순간이동 했을 경우 시간 증가 없이 다시 queue에 넣기
5. X - 1, X + 1 즉 걸어서 이동할 경우 시간을 1 증가시켜 queue에 넣기


3️⃣ 나의 코드

const [N, K] = require("fs").readFileSync("./dev/stdin").toString().trim().split(" ").map(Number);
const visited = new Array(100001).fill(0);

function bfs(N, K) {
	const queue = [];
	queue.push([N, 0]);
	visited[N] = 1;

	while (queue.length) {
		let [X, time] = queue.shift();
		if (X === K) {
			console.log(time);
			return;
		}

		for (const position of [2 * X, X - 1, X + 1]) {
			if (!visited[position] && position >= 0 && position <= 100000) {
				visited[position] = 1;
				if (position === 2 * X) {
					queue.push([position, time]);
				} else {
					queue.push([position, time + 1]);
				}
			}
		}
	}
}

bfs(N, K);

4️⃣ 마무리

2 * X, X - 1, X + 1의 순서를 바꿀 경우 오답 처리 된다 (이것 때문에 오답 파티) 최소 시간을 구해야하기 때문에 시간 증가가 없는 2 * X가 제일 먼저 오는 것 까지는 이해가 됐지만, X - 1, X + 1의 순서는 무슨 연관이 있는지 모르겠다

최소, 최단을 구할 땐 visited를 만들어 갔던 위치에 다시 가지 못하게 해야 시간초과가 나지 않고 문제가 풀림