BOJ - 숨바꼭질

BOJ - 숨바꼭질

Link

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

접근 방식

• 첫 번째 줄에서 입력값을 받아 초기 위치 n과 동생의 위치 k를 구한다.
• 최단 시간 저장을 위해 MAX 크기의 visited 배열을 생성하여 각 위치까지의 최단 시간을 저장한다.
• 현재 위치에서 이동할 수 있는 세 가지 경우(1칸 앞, 1칸 뒤, 현재 위치 X 2)에 대해 BFS를 수행한다.
• 도달 가능하고 아직 도달하지 않은 곳에 도달 시 현재 위치에 대한 도달 시간 + 1을 해당 위치에 대한 최단 시간으로 기록하며 visited 배열을 채워간다.
• k에 대한 최단시간을 출력한다.

Code

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

const MAX = 100001;
let [n, k] = input[0].split(" ").map(Number);
let visited = new Array(MAX).fill(0);

class Queue {
  constructor() {
    this.items = {};
    this.headIdx = 0;
    this.tailIdx = 0;
  }

  enqueue(item) {
    this.items[this.tailIdx] = item;
    this.tailIdx++;
  }

  dequeue() {
    const item = this.items[this.headIdx];
    delete this.items[this.headIdx];
    this.headIdx++;
    return item;
  }

  peek() {
    return this.items[this.headIdx];
  }

  getLength() {
    return this.tailIdx - this.headIdx;
  }
}

function bfs() {
  queue = new Queue();
  queue.enqueue(n);

  while (queue.getLength() != 0) {
    let cur = queue.dequeue();
    if (cur == k) {
      return visited[cur];
    }
    for (let nxt of [cur - 1, cur + 1, cur * 2]) {
      if (nxt < 0 || nxt >= MAX) continue;
      if (visited[nxt] == 0) {
        visited[nxt] = visited[cur] + 1;
        queue.enqueue(nxt);
      }
    }
  }
}

console.log(bfs());