[자바스크립트] 1697 숨박꼭질

1697번: 숨박꼭질

문제

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

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

 

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

예제 입력 1

5 17

 

 

예제 출력 1

4

자료구조

① 문자열: str

② 정수: n, count

 

 

알고리즘

① 초기화: 시작 위치 N을 큐에 추가하고, 방문 배열 visited의 해당 위치를 0으로 설정한다.

② 탐색 루프: Queue가 빌 때까지 반복한다.

• 현재 위치 `x`를 큐에서 제거합니다.
• 현재 위치 `x`가 목표 위치 `K`와 같으면 방문 횟수를 반환하고 종료합니다.
• 현재 위치 `x`에서 갈 수 있는 세 가지 경우(앞으로 한 칸, 뒤로 한 칸, 두 배 위치)를 모두 탐색한다.
  • 해당 위치가 범위 내에 있고 아직 방문하지 않은 경우에만 큐에 추가하고 방문 배열을 갱신.

③ 반환: 목표 위치에 도달했을 때의 방문 횟수를 반환한다.

 

 

소스 코드 1

const fs = require("fs");
const [N, K] = fs.readFileSync("./input.txt").toString().split(" ").map(Number);
const MAX = 100001;
const visited = Array(MAX).fill(0);

function bfs() {
  const queue = [N];

  while (queue.length) {
    const x = queue.shift();
    if (x === K) return visited[x];

    for (let node of [x - 1, x + 1, x * 2]) {
      if (node < 0 || MAX <= node) continue;

      if (!visited[node]) {
        queue.push(node);
        visited[node] = visited[x] + 1;
      }
    }
  }
}

console.log(bfs());

560ms

 

 

 

✔ 출처

https://www.acmicpc.net/problem/1697