[백준] 1697번 : 숨바꼭질 (실버Ⅰ) by node.js

1697번: 숨바꼭질

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

www.acmicpc.net

▷ 해결 날짜 : 2022.07.03
▷ 소요 시간 : 1시간
▷ 풀이 과정 :

숨바꼭질을 할 때 술래는 걸어서 (X - 1, X + 1) 만큼 이동할 수 있고 순간이동을 하여 (X * 2) 만큼 이동할 수 있다고 한다.

여기서 술래(수빈이) 와 동생이 숨바꼭질을 하는데, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제이다.

문제만 보면 사실 어떻게 풀어야 하는지 막막하기만 한데, 풀이 방향만 잘 잡아보면 그렇게 구현하는데 어려움이 있는 문제는 아니었다.

쉽게 저 3가지의 경우의 수를 계속해서 체크해 주기만 하면 문제가 해결된다.

여기서 경우의 수를 체크할 때 주의 사항은

값의 범위는 0 ~ 100000이다.
한번 방문한 위치는 다시 고려하지 않는다.
이동할 때마다 시간이 1초씩 걸린다.

▷ 구현

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

const [N, K] = input[0].split(" ").map(Number);
const visited = [...Array(100001)].fill(0);

const getFastestFindTime = (start, end) => {
  const queue = [[start, 0]];
  while (queue.length) {
    const [pos, time] = queue.shift();
    if (visited[pos]) continue;
    if (pos === end) return time;
    for (const move of [pos + 1, pos - 1, pos * 2]) {
      !visited[move] &&
        move >= 0 &&
        move <= 100000 &&
        queue.push([move, time + 1]);
    }
    visited[pos] = 1;
  }
};

console.log(getFastestFindTime(N, K));

▷ 복기 :

문제 구현 난이도 자체는 어렵지 않았는데, 이 구현 방향을 잡는게 감이 안잡혀 생각보다 많은 시간을 소비하였다.