백준 | 1697번 숨바꼭질 (JavaScript 풀이)

BFS로 최단거리 찾기

문제 소개

백준 1697번 "숨바꼭질"은 BFS(너비 우선 탐색)를 이용한 최단거리 찾기의 대표적인 문제입니다.

문제 요약

• 수빈이는 현재 점 N에 있고, 동생은 점 K에 있음
• 1초마다 3가지 이동 가능:
  • X-1 (뒤로 한 칸)
  • X+1 (앞으로 한 칸)
  • X×2 (순간이동)
• 동생을 찾는 최단 시간 구하기

예제

입력: 5 17
출력: 4

경로: 5 → 10 → 9 → 18 → 17 (4초)

---

왜 BFS를 사용해야 할까?

BFS vs DFS 비교

구분	BFS	DFS
탐색 방식	너비 우선 (층별로)	깊이 우선 (한 길로)
최단거리	✅ 보장	❌ 보장 안됨
구현	Queue 사용	재귀/Stack 사용
메모리	많이 사용	적게 사용

---

BFS가 최단거리를 보장하는 이유

시간 0: [5]
시간 1: [4, 6, 10]        ← 1초 만에 갈 수 있는 모든 곳
시간 2: [3, 8, 7, 12, 9, 11, 20]  ← 2초 만에 갈 수 있는 모든 곳
시간 3: [...]             ← 3초 만에 갈 수 있는 모든 곳
시간 4: [...17...]        ← 17에 처음 도달! (최단시간)

핵심: 물결이 퍼지듯이 가까운 곳부터 탐색하므로, 목표에 처음 도달하는 순간이 최단거리!

---

문제 접근 방법

Step 1: 문제 분석

javascript

// 매 초마다 가능한 이동
현재 위치: X
1초 후 가능한 위치: [X-1, X+1, X×2]

// 제약 조건
0 ≤ N, K ≤ 100,000

---

Step 2: 알고리즘 설계

1. 큐에 시작점 넣기: queue = [[N, 0]] (위치, 시간)
2. 방문 체크 배열 생성: 중복 방문 방지
3. BFS 탐색:
   • 큐에서 하나씩 꺼내기
   • 3가지 이동 시도
   • 목표 도달 시 종료
   • 미방문 위치는 큐에 추가

---

Step 3: 시각적 이해

    [5]           시작
     ↓
[4] [6] [10]      1초 후
     ↓
    ...           계속 탐색
     ↓
   [17]           4초 후 도달!

---

💻 전체 코드 구현

기본 구현

javascript

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

const [N, K] = input.map(Number);

// 같은 위치면 0초
if (N === K) {
    console.log(0);
    return;
}

// BFS 초기 설정
const queue = [[N, 0]];  // [위치, 시간]
const visited = new Array(100001).fill(false);
visited[N] = true;

let front = 0;  // 큐 인덱스 (shift 대신 사용)

// BFS 탐색
while (front < queue.length) {
    const [pos, time] = queue[front++];
    
    // 3가지 이동 방법
    const nextPositions = [pos - 1, pos + 1, pos * 2];
    
    for (const next of nextPositions) {
        // 목표 도달!
        if (next === K) {
            console.log(time + 1);
            return;
        }
        
        // 범위 체크 & 방문 체크
        if (next >= 0 && next <= 100000 && !visited[next]) {
            visited[next] = true;
            queue.push([next, time + 1]);
        }
    }
}

---

최적화된 구현

javascript

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

const [N, K] = input.map(Number);

// 예외 처리: 같은 위치
if (N === K) {
    console.log(0);
    process.exit(0);
}

// 예외 처리: N > K인 경우 (뒤로만 이동)
if (N > K) {
    console.log(N - K);
    process.exit(0);
}

const MAX = 100000;
const visited = new Array(MAX + 1).fill(-1);  // -1: 미방문, 0이상: 도달 시간
visited[N] = 0;

const queue = [N];
let front = 0;

while (front < queue.length) {
    const pos = queue[front++];
    const time = visited[pos];
    
    // 3가지 이동 시도
    for (const next of [pos - 1, pos + 1, pos * 2]) {
        // 목표 도달
        if (next === K) {
            console.log(time + 1);
            process.exit(0);
        }
        
        // 유효 범위 & 미방문
        if (next >= 0 && next <= MAX && visited[next] === -1) {
            visited[next] = time + 1;
            queue.push(next);
        }
    }
}

---

코드 상세 설명

1. 큐 최적화

javascript

// ❌ 비효율적 (shift는 O(n))
const current = queue.shift();

// ✅ 효율적 (인덱스 사용은 O(1))
const current = queue[front++];

---

2. 방문 체크의 중요성

javascript

// 방문 체크를 안 하면?
5 → 4 → 5 → 4 → ... (무한 반복!)

// 방문 체크를 하면
5 → 4 (4 방문 표시)
5 → 6 (6 방문 표시)
4는 이미 방문했으므로 다시 가지 않음

---

3. 범위 체크 필수

javascript

// 범위를 벗어나면 배열 에러!
if (next >= 0 && next <= 100000) {
    // 안전한 범위
}

---

시간복잡도 분석

• 시간복잡도: O(N)
  • 최대 100,001개의 위치를 한 번씩 방문
  • 각 위치에서 3가지 이동 확인 = O(3N) = O(N)
• 공간복잡도: O(N)
  • visited 배열: 100,001 크기
  • queue: 최대 100,001개 요소

---

핵심 정리

BFS 최단거리 템플릿

javascript

// 1. 초기화
const queue = [[start, 0]];
const visited = new Array(MAX).fill(false);
visited[start] = true;

// 2. BFS 탐색
while (queue.length > 0) {
    const [current, time] = queue.shift();
    
    // 3. 다음 위치들 확인
    for (const next of getNextPositions(current)) {
        // 4. 목표 확인
        if (next === target) return time + 1;
        
        // 5. 방문 체크 & 큐 추가
        if (isValid(next) && !visited[next]) {
            visited[next] = true;
            queue.push([next, time + 1]);
        }
    }
}

---

마무리

"숨바꼭질" 문제는 BFS의 최단거리 특성을 보여주는 대표적인 문제입니다.

 

요약:

1. BFS는 가중치가 같은 그래프에서 최단거리 보장
2. 방문 체크로 중복 방지
3. 범위 체크로 에러 방지
4. 큐 최적화로 성능 향상