[Node.js] BOJ - 1697 숨바꼭질

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

1697번: 숨바꼭질

 

문제

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

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

풀이

해당 문제는 간선의 비용이 1초로 동일한 상황에서 최단거리를 구하는 문제로써 BFS 알고리즘을 사용하면 해결할 수 있는 문제이다.

1. 최대 위치 값이 100000이므로 방문 여부를 값을 담기 위한 방문 배열을 100001 크기만큼 생성한다.

2. 큐를 생성하고 수빈의 현재위치 값을 넣어준다.

3. 큐의 길이가 0일 때까지 반복하되 현재 위치 값이 동생의 위치와 일치할 경우 while 반복문에서 탈출한다. 

4. 현재위치 + 1 , 현재위치 - 1 , 현재위치  * 2 한 값이 공간을 벗어난 경우 continue 로 넘어가고 방문하지 않은 경우 다음 위치로 큐에 넣어주기전에 +1 초씩 소요 시간을 더해주며 3번 과정을 반복한다.

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return this.tailIndex - this.headIndex;
  }
}

const MAX = 100001;
const [n, k] = input[0].split(' ').map(Number); // 초기 수빈이의 위치(N)과 동생의 위치(K)
let visited = new Array(MAX).fill(0); // 각 위치까지의 최단 시간

function bfs() {
  let 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]) {
      // 공간을 벗어난 경우 continue
      if (nxt < 0 || nxt >= MAX) continue;
      // 아직 방문하지 않은 위치라면
      if (visited[nxt] == 0) {
        visited[nxt] = visited[cur] + 1;
        queue.enqueue(nxt);
      }
    }
  }
}
console.log(bfs());