1697.md

숨바꼭질

문제

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

정답

let [N, K] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .split(" ").map(Number)

let visited = Array.from({ length: 100001 }, () => false)
let queue = [[N, 0]]

while (queue.length) {

  // 현재 위치와 깊이를 가져온다.
  const [cur, dep] = queue.shift()

  // 이미 방문한 곳이면 넘어간다.
  if (visited[cur]) continue

  // 방문하지 않았다면 방문처리를 한다.
  visited[cur] = true

  if (cur === K) {
    console.log(dep)
    break
  }

  // 모든 경우를 구한다.
  for (let next of [cur + 1, cur - 1, cur * 2]) {
    if (!visited[next] && next >= 0 && next <= 100000) {
      // 처음 순회할 때 queue에 [6,1], [4,1], [10,1]이 들어간다.
      // 그 다음 while()문의 경우 cur = 6, dep = 1이 된다. 그 후 queue에 [4,1] [10,1] [7,2] [12, 2]가 저장된다. (5,2)는 이미 방문한 곳이므로 넘어간다.
      // ...
      // 그 다음 while()문의 경우 cur = 7, dep = 2가 된다. 그 후 queue에 [12, 2] [3, 2] [8, 2] [11, 2] [9, 2] [20, 2] [8, 3] [14, 3]이 저장된다.
      // ...
      // 결과적으로 모든 경우의 수를 순회하며 가장 먼저 K에 도달한 경우의 깊이를 알 수 있게 된다.
      queue.push([next, dep + 1])
    }
  }