[백준] 1697. 숨바꼭질 (자바스크립트/js/javascript/node.js/BFS)

 

일단 BFS 알고리즘을 이용하기 전에 먼저 확인해주어야 할 조건이 있다.

1. 수빈과 동생의 위치가 다르면

  1) 수빈의 위치 > 동생의 위치

    answer = 수빈 - 동생

  2) 큐에 수빈 - 1, 수빈 + 1, 2 * 수빈을 각각 넣고 BFS 실행

2. 수빈과 동생의 위치가 같으면

   answer = 0

 

수빈과 동생의 위치가 같다면 답은 볼 것도 없이 0초 만에 동생을 찾을 수 있다.

수빈과 동생의 위치가 다르다면, 그리고 그 안에서 수빈의 위치가 동생의 위치보다 더 크다면 답은 수빈의 위치 - 동생의 위치가 된다. 왜냐하면 예를 들어 수빈의 위치가 9, 동생의 위치가 5라면 수빈의 위치가 줄어들어야 하므로 줄어들기 위해서는 수빈 - 1 만 계속 해주어야 하기 때문이다.

그래서 나머지 경우에만 BFS를 실행하는데 이 때 미리 큐에 수빈 - 1, 수빈 + 1, 2 * 수빈을 넣고 BFS를 실행한다.

이 때 반복문을 돌리기 전에 이미 이 안에 답이 있다면 answer = 1로 바꾸고 반복문을 탈출한다. 그렇지 않다면 방문했다는 visited 객체에 1을 넣어준다. (처음에 1초가 지났을 때의 값들이기 때문)

그 다음 while문을 돌리는데 큐 안에 값이 들어있으며, 그리고 답을 아직 찾지 못했다면 반복문이 진행된다.

큐에서 맨 처음 원소를 뺀 후 그 원소를 target이라 하면 target - 1 , target - 2, 2*target 중에서  방문한 적이 없다면 큐에다 넣으면 되는데, 이 때 시간초과를 막기 위해 양수부터 동생의 위치의 2배까지에 해당한다면 큐에 넣는 것으로 범위를 좁혀준다. 어차피 음수라면 볼 것도 없고, 동생의 위치의 2배보다 커져버린다면 그것 또한 역시 볼 필요가 없기 때문이다.

그렇게 해서 큐에다가 넣을 때 방문처리를 현재 target의 visited 값보다 1큰 값을 저장하면 된다. 그러면 그게 몇 번째에 방문했는지가 되는 것이다.

 

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split(" ");
const subin = Number(input[0]); // 수빈이 있는 위치
const sister = Number(input[1]); // 동생이 있는 위치
let answer;

const BFS = (queue) => {
  let findAnswer = false;
  const visited = {};
  visited[subin] = 0;
  for (let element of queue) {
    if (element >= 0) {
      if (element === sister) {
        answer = 1;
        findAnswer = true;
        break;
      }
      visited[element] = 1;
    }
  }
  while (queue.length && !findAnswer) {
    const target = queue.shift();
    const nexts = [target - 1, target + 1, 2 * target];
    for (let next of nexts) {
      if (visited[next] === undefined && next <= 2 * sister && next >= 0) {
        if (next === sister) {
          answer = visited[target] + 1;
          findAnswer = true;
          break;
        }
        queue.push(next);
        visited[next] = visited[target] + 1;
      }
    }
    if (findAnswer) {
      break;
    }
  }
};

if (subin !== sister) {
  // 수빈과 동생의 위치가 다른 경우
  if (subin > sister) {
    // 수빈의 위치가 동생보다 큰 경우
    answer = subin - sister;
  } else {
    const queue = [subin - 1, subin + 1, subin * 2];
    BFS(queue);
  }
} else {
  // 수빈과 동생의 위치가 같으면
  answer = 0;
}
console.log(answer);