💡문제 분석 요약

• 수빈이가 현재 위치 N에 있고, 동생이 위치 K에 있다.
• 수빈이는 1초마다 세 가지 방법으로 이동할 수 있다:
  1. 한 칸 앞으로 이동: N+1
  2. 한 칸 뒤로 이동: N−1
  3. 두 배로 이동: N×2
• 수빈이가 동생의 위치 K까지 가는 최소 시간을 구해야 한다.
• 가중치가 동일한 그래프에서 최단 경로를 구하는 문제이므로 BFS(너비 우선 탐색)로 풀 수 있다.

💡알고리즘 설계

• BFS를 사용하여 최단 시간을 구한다.
  • BFS는 현재 노드에서 갈 수 있는 모든 노드를 탐색한 후, 다음 레벨로 넘어가기 때문에, 여러 경로 중에서 최단 경로를 찾아주는 특성이 있다.
• 수빈이의 위치 N에서 시작하여, 매 순간 갈 수 있는 세 가지 위치(앞으로, 뒤로, 두 배)를 모두 큐에 넣어 탐색한다.
• 방문한 위치를 기록하여 같은 위치를 중복으로 방문하지 않게 한다.
• 목표 지점 K에 도달하면 그때까지 걸린 시간을 반환한다.

💡코드

const fs = require('fs');
const path = require('path');

const inputPath = path.join(__dirname, 'input.txt');
const input = fs.readFileSync(inputPath, 'utf-8').trim().split(' ');

// 입력값 파싱
const [N, K] = input.map(Number);

// 값이 올바르게 파싱되었는지 확인
if (isNaN(N) || isNaN(K)) {
  console.error("입력 값이 잘못되었습니다. N과 K를 올바르게 입력하세요.");
  process.exit(1);
}

function hideAndSeek(N, K) {
  if (N === K) return 0; // 출발점과 도착점이 같으면 0초
  
  const visited = Array(100001).fill(false); // 방문 여부 체크 배열
  const queue = [[N, 0]]; // [현재 위치, 걸린 시간]을 저장하는 큐
  visited[N] = true; // 출발점 방문 처리
  
  while (queue.length > 0) {
    const [current, time] = queue.shift();
    
    // 세 가지 경우를 탐색
    for (let next of [current - 1, current + 1, current * 2]) {
      if (next === K) return time + 1; // 목표 지점에 도달하면 시간 반환
      
      // 범위를 벗어나지 않고 방문하지 않은 위치일 경우 큐에 추가
      if (next >= 0 && next <= 100000 && !visited[next]) {
        visited[next] = true; // 방문 처리
        queue.push([next, time + 1]); // 큐에 [위치, 시간] 추가
      }
    }
  }
}

console.log(hideAndSeek(N, K)); // 결과 출력

💡시간복잡도

• BFS의 시간 복잡도는 O(V + E)
  • 여기서 V는 정점의 개수, E는 간선의 개수
    • 정점의 개수 V: 위치는 최대 100,000까지이므로 최대 100,001개의 정점을 탐색할 수 있다.
    • 간선의 개수 E: 각 정점에서 최대 3개의 인접한 정점(앞으로, 뒤로, 두 배)이 있다. 따라서 시간 복잡도는 O(3V) → O(V)