[baekjoon] 12851 숨바꼭질2 (Javascript)

Cafe Mocha 2023. 2. 3. 14:49

12851번: 숨바꼭질 2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

알고리즘 : bfs

bfs는 2차원에 익숙해서 그외의 경우가 더어렵다고 느껴진다.

이번 문제는 max값을 설정하지 않아서 고생했다.

로직은 맞는데 자꾸 틀려서 max값을 문제의 최대값 *2로 변경했더니 풀린다!

예외처리에 집중하자!!

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .split("\n")
    .map((val) => val.trim());

  let [n, k] = input
    .shift()
    .split(" ")
    .map((v) => +v);

  let max = 200000;

  // 1초후 x-1 or x+1
  // 1초후 2*x

  let ans = new Array(max + 4).fill(0);
  let vis = new Array(max + 4).fill(0);

  // 모든 경우의 수를 확인? ->2초 가능할듯

  const check = (start, end) => {
    let queue = [];
    vis[start] = 1;
    ans[start] = 1;
    queue.push(start);
    while (queue.length) {
      let cx = queue.shift();
      for (let dir = 0; dir < 3; dir++) {
        let nx;
        if (dir === 0) nx = cx * 2;
        else if (dir === 1) nx = cx + 1;
        else nx = cx - 1;

        if (nx >= 0 && nx < max) {
          if (!vis[nx]) {
            queue.push(nx);
            vis[nx] = vis[cx] + 1;
            ans[nx] += ans[cx];
          } else if (vis[nx] === vis[cx] + 1) {
            ans[nx] += ans[cx];
          }
        }
      }
    }
  };

  check(n, k);

  console.log(vis[k] - 1);
  console.log(ans[k]);
}

solution();