숨바꼭질3

숨바꼭질 3

문제 설명

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

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

예제 입력

5 17

예제 출력

2

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  const [N, K] = input[0].split(" ").map(Number);
  const visited = Array.from({ length: 100001 }, () => false);

  const bfs = () => {
    let queue = [[N, 0]];
    visited[N] = true;

    while (queue.length > 0) {
      const [cur, time] = queue.shift();
      if (cur === K) return time;

      const next = [cur * 2, cur - 1, cur + 1];

      for (let i = 0; i < 3; i++) {
        if (0 <= next[i] && next[i] <= 100001 && !visited[next[i]]) {
          visited[next[i]] = true;
          if (next[i] === cur * 2) {
            queue.unshift([next[i], time]);
          }
          if (next[i] === cur - 1) {
            queue.push([next[i], time + 1]);
          }
          if (next[i] === cur + 1) {
            queue.push([next[i], time + 1]);
          }
        }
      }
    }
  };
  result = bfs();
  console.log(result);
};

solution(input);

아이디어 / 접근법

1. 시작 좌표에서 끝 좌표까지 계속 이동하면서 시간 누적
2. 방문체크 하면서 탐색
3. 경우에 따라서 다르게 처리 *2일 경우 +0초 아닐 경우 +1초
4. 끝

후기

숨바꼭질 마스터했다고 생각해서 빠르게 풀어야지 하고 풀었다 실제로 답은 진짜 10분도 안 걸려서 나왔는데 계속 엄청 틀리더라.. 1시간 붙잡다가 찾아봤는데 로직 순서가 중요하다고 한다.. 그 전까지는 안그랬는데 0초일 경우 즉 *2 의 경우 일때는 push 가 아닌 대가리 쪽에 넣어서 우선순위를 높여야 하는 우선순위 큐 + BFS 문제였다. 역시 골드 문제는 괜히 골드 문제가 아니구나 너무 어렵다...