BOJ - 숨바꼭질

문제

BOJ — 숨바꼭질

접근 방법

위치 x에서 x - 1, x + 1, 2 * x로 이동하는 데 각각 1초가 걸린다. 모든 이동 비용이 같으므로 BFS로 각 위치까지의 최단 시간을 구할 수 있다.

거리 배열은 미방문을 뜻하는 -1로 초기화하고, 시작점만 0으로 설정한다. 미방문과 시작점의 거리를 모두 0으로 표현하면 시작점이 다시 큐에 들어갈 수 있다. 다음 위치를 발견하는 즉시 거리를 기록해 중복 방문을 막는다.

큐는 배열과 읽기 인덱스로 구현한다. shift()로 매번 배열 앞을 제거하지 않고 인덱스를 증가시키면 각 원소를 한 번씩 처리할 수 있다. 목표 위치를 꺼냈을 때 저장된 거리가 답이다.

탐색 범위는 0부터 100,000까지로 제한한다. 음수로 이동해도 더 빠른 경로가 생기지 않는다. 상한을 넘는 첫 이동은 순간이동 또는 100,000에서 한 칸 전진하는 경우인데, 전진은 되돌아오는 우회다. 순간이동으로 상한을 넘었다면 목표까지 감소해야 하므로, 순간이동 전에 감소하거나 바로 걸어가는 경로로 대체할 수 있다.

코드

const fs = require('fs')
const [n, k] = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number)
const LIMIT = 100000

function shortestTime(start, target) {
  const distance = Array(LIMIT + 1).fill(-1)
  const queue = [start]
  let head = 0
  distance[start] = 0

  while (head < queue.length) {
    const current = queue[head++]
    if (current === target) return distance[current]

    for (const next of [current - 1, current + 1, current * 2]) {
      if (next < 0 || next > LIMIT || distance[next] !== -1) continue
      distance[next] = distance[current] + 1
      queue.push(next)
    }
  }
}

console.log(shortestTime(n, k))

복잡도와 경계 조건

탐색 가능한 위치 수를 L이라 하면 시간과 추가 공간은 모두 O(L)이다. 각 위치에서 확인하는 이동은 최대 세 가지다.

시작점과 목표가 같으면 0초다. 위치 0에서는 순간이동 결과도 0이지만 이미 방문한 위치이므로 다시 큐에 넣지 않는다. 상한인 100,000도 유효한 인덱스에 포함한다.