숨바꼭질 4

숨바꼭질 4

문제 설명

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

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

예제 입력

5 17

예제 출력

4
5 10 9 18 17

---

문제 풀이

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 temp = Array.from({ length: 1000001 }, () => 0);
  const visited = Array.from({ length: 1000001 }, () => false);

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

    while (queue.length > head) {
      const [cur, time] = queue[head++];

      if (cur === K) return time;

      for (let nx of [cur * 2, cur - 1, cur + 1]) {
        if (0 <= nx && nx <= 1000001 && !visited[nx]) {
          temp[nx] = cur;
          visited[nx] = true;

          queue.push([nx, time + 1]);
        }
      }
    }
  };

  let k = bfs();
  const solve = (num) => {
    const path = [];
    path.push(K);
    let before = temp[K];
    for (let i = 0; i < num; i++) {
      path.push(before);
      before = temp[before];
    }
    return path;
  };
  const path = solve(k);
  path.reverse();

  console.log(k);
  console.log(path.join(" "));
};
solution(input);

아이디어 / 접근법

1. 시작 좌표에서 끝 좌표까지 계속 이동하면서 시간 누적
2. 방문체크 하면서 탐색 및 부모 좌표 즉 이전 좌표 저장
3. 경우에 따라서 다르게 처리 *2일 경우 +0초 아닐 경우 +1초
4. 반복문을 통해 좌표 출력

후기

이 문제는 진짜 어떻게 풀이해야 할 지 감이 되게 안왔다. 어떻게 하면 경로를 추적해서 답을 찾을 수 있을까? 가 고민이었는데 그 문제는 배열을 하나 만들어서 이전 좌표 값을 현재 index 값에 저장하면 될 것이라고 생각했다. 근데 이 문제도 자꾸 답이 틀리길래 봤더니 이 문제 또한 우선순위가 중요한 문제 였다.