숨바꼭질

문제 설명

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

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

입력

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

출력

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

문제 풀이

여러가지 방법을 시도해서 풀어봤다. 하지만 기본적으로 모든 풀이의 큰 틀은 같다.

1. bfs를 구현.
   1. queue에 시작점(수빈 위치)를 넣고 시작한다.
   2. queue가 0이 될 때까지 while문.
      1. position에 +1,-1,*2을 하고나서, 각각 값이 동생의 위치와 같은지 확인하고 같으면 visited배열의 값을 찍고 함수를 끝낸다.
      2. 비정상적인 값(0보다 작거나, 100000을 넘는 경우는 continue, 그리고 중복을 제거하기 위한 visited배열이 -1이 아니면 continue)을 제외한다.
      3. 정상적인 값이면 queue에 push.

위와 같이 구현해서 실행하면 값은 정상적으로 나온다. 하지만 디테일한 부분에서 시간 초과를 경험했다.

1. 수빈의 위치와 그때의 시간을 배열로 만들어 queue에 넣어서 사용한 경우.

const visited = Array(100001).fill(false);

const excuteBFS = () => {
  const queue = [[subinPosition, 0]];
  visited[subinPosition] = true;
  while (queue.length !== 0) {
    const [position, time] = queue.shift();
    if (position === brothoerPosition) {
      console.log(time);
      return;
    }
    for (let i = 0; i < 3; i++) {
      let nx = 0;
      if (i === 2) nx = position * 2;
      else nx = position + dx[i];
      if (nx < 0 || nx > 100001) continue;
      if (visited[nx]) continue;
      visited[nx] = true;
      queue.push([nx, time + 1]);
    }
  }
};

위의 경우에는 시간초과가 일어났다. 이유는 자바스크립트에서 shift()는 배열을 이용한 것이기 때문에,
queue에 많은 값이 들어가 있으면 인덱스의 처리 때문인지(확실하게는 모르겠다.) 느리게 작동한다.
그래서 이 경우에는 LinkedList로 queue를 구현해서 사용하면 정답 코드가 나온다.
그래서 처음에는 자바스크립트 arr로는 구현할 수 없는 문제인줄 알았다. 하지만 아니였다.

정답 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  insert(value) {
    const node = new Node(value);
    if (this.head === null) {
      this.head = node;
      this.tail = this.head;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
  }

  shift() {
    const tempNode = this.head;
    this.head = this.head.next;
    this.length--;
    return tempNode;
  }
}

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

const dx = [1, -1];
const [subinPosition, brothoerPosition] = input.map(position =>
  Number(position)
);

const visited = Array(100001).fill(false);

const excuteBFS = () => {
  const queue = new Queue();
  queue.insert([subinPosition, 0]);
  visited[subinPosition] = true;
  while (queue.length !== 0) {
    const [position, time] = queue.shift().value;
    if (position === brothoerPosition) {
      console.log(time);
      return;
    }
    for (let i = 0; i < 3; i++) {
      let nx = 0;
      if (i === 2) nx = position * 2;
      else nx = position + dx[i];
      if (nx < 0 || nx > 100001) continue;
      if (visited[nx]) continue;
      visited[nx] = true;
      queue.insert([nx, time + 1]);
    }
  }
};

excuteBFS();

2. 수빈 위치와 시간을 배열로 저장하지 않는 경우.

const visited = Array(100001).fill(-1);

const excuteBFS = () => {
  const queue = [];
  queue.push(subinPosition);
  visited[subinPosition] = 0;
  while (queue.length !== 0) {
    const position = queue.shift();
    for (let i = 0; i < 3; i++) {
      let nx = 0;
      if (i === 2) nx = position * 2;
      else nx = position + dx[i];
      if (nx === brothoerPosition) {
        console.log(visited[position] + 1);
        return;
      }
      if (nx < 0 || nx > 100001) continue;
      if (visited[nx] !== -1) continue;
      visited[nx] = visited[position] + 1;
      queue.push(nx);
    }
  }
};

이 코드의 경우 속도가 조금 느리긴 하지만 역시 통과했다.
다른 점이라면, [수빈위치,시간] 배열을 만들어서 queue에 넣어준 것이 아니라,
visited배열을 true,false가 아닌 시간을 저장하고, queue에도 수빈의 위치만 넣어서 사용한 방법이다.
이 방법은 시간초과도 나지 않고, 잘 돌아간다.
이 부분에서 배열을 만들고 queue에 넣고 queue에서 빼고 그 값을 다시 사용하고 하는 과정에서 시간이 오래 걸려서 시간 초과가 나는게 아닐까 생각해본다.

결론

여러 가지 방법으로 시도해서 문제를 풀어 봤는데, 가장 좋은 방법은 두 가지 방법을 합치는 것이다. 당연하게 두 가지 방법을 채택한 방법이 가장 빠르다.
하지만, 첫 번째 방법은 Queue를 직접 구현해서 사용해야하기 때문에 실제 코딩테스트에서는 적합하지 않은 방법일 것이다.
코딩 테스트에서는 시간을 생각한다면 두 번째 방법을 채택해서 푸는 것이 더 좋을 것 같다.

추가

백준에서 자바스크립트를 푸신 분 중 속도가 제일 빠른 분의 코드를 보면 방법은 비슷하지만, 함수를 만들어 푸시지 않고 전역으로 푸신 분이 있다. 그리고 나처럼 for문을 이용해서 +1,-1,*2하지 않고 if else문으로 했다. visited 배열 또한 for문을 이용해서 push 해주셨다.
이 코드가 180ms로 가장 빠른 코드였는데, 가정들을 몇 개 해봤다.

1. for문을 사용해서 +1,-1,*2 하는 것 보다 if else가 빠르다.
   • 이 가정은 틀린 가정이였다. 같은 코드를 for, if else로 해봤지만 속도가 비슷했다.
2. Array(N).fill보다 for문을 사용하는게 빠르다.
   • 이것도 틀린 가정이였다. 둘 다 속도는 비슷하다.
3. const excuteBFS 처럼 함수를 선언을 하지 않아서 빠르다.
   • 이것도 틀린 가정이였다. 둘 다 속도는 비슷했다.

그럼 뭐가 문제였던걸까?

문제는 그냥 백준에서 테스트 케이스가 많아지거나 한 것 같다..

동일한 코드를 먼저 돌려봤어야 하는데 동일한 코드를 돌려보니 현재는 400ms정도가 나온다.
아무튼 결론은 허무했지만, 어떤 차이가 있는지 그래도 어렴풋이 알았으니 이득(?)봤다.
가장 빠른 코드는,

queue에 배열로 푸시하지말고 값을 푸시. 그리고 queue를 linkedlist로 구현.

위의 방법이였다.

주의!

임의로 혼자서 돌려본 것이기 때문에 정확하지 않을 수 있다.
내가 비슷하다 혹은 아니라고 생각했던 것들이 맞는 결과일수도 있으니 다시 생각해볼것.