[코딩 테스트, 더 이상 미룰 수 없다] BOJ 1697 숨바꼭질 — "Hello, BFS World!"

백준 1697 숨바꼭질은 BFS의 대표적인 입문 문제다.
하지만 단순히 “최단거리니까 BFS”라고 외우기보다는 왜 BFS가 맞는지를 스스로 납득하는 과정이 중요하다.

이 글에서는 문제를 보고 어떤 사고 과정을 통해 BFS로 접근하게 되었는지 정리해보았다.

---

1. 문제 요약

수빈이는 현재 위치 N에 있고, 동생은 K에 있다.

수빈이는 다음 세 가지 방법으로 이동할 수 있다.

X → X - 1
X → X + 1
X → 2 * X

모든 이동은 1초가 걸린다.

목표는

동생을 찾는 최소 시간을 구하는 것이다.

---

2. 처음 들었던 의문 — 그리디 아닌가?

처음 문제를 보면 이런 생각이 들 수 있다.

• K보다 작으면 *2가 빠르지 않을까?
• K보다 크면 -1 하면 되지 않을까?

즉 현재 목표에 가까워지는 선택을 계속 하면 되지 않을까?
라는 생각이 자연스럽게 나온다.

하지만 실제로는 그렇지 않다.

예를 들어

N = 5
K = 17

직관적으로는

5 → 10 → 20 → 19 → 18 → 17

처럼 가고 싶지만

더 빠른 경로는

5 → 4 → 8 → 16 → 17

이다.

즉 목표와 잠깐 멀어지는 선택이 오히려 최단경로가 될 수 있다.

이 순간

그리디 방식은 사용할 수 없다는 결론에 도달했다.

---

3. 그래프로 생각하기

문제를 다시 보면 사실 이것은 그래프 문제이다.

각 숫자를 노드라고 생각하면

X
├─ X-1
├─ X+1
└─ 2X

이렇게 연결된다.

예를 들어 5라면

5
├─4
├─6
└─10

즉 우리는

그래프에서 N → K까지의 최단거리를 구하고 있다.

---

4. 이동 비용이 모두 동일하다

이 문제에서 중요한 조건이 하나 있다.

모든 이동 = 1초

그래프 이론에서

모든 간선의 가중치가 동일한 최단거리 문제

는 BFS로 해결할 수 있다.

왜냐하면 BFS는 탐색을 이렇게 진행하기 때문이다.

거리 0
거리 1
거리 2
거리 3
...

즉 레벨 순서로 탐색한다.

그래서 어떤 위치에 처음 도착한 순간이 곧 최단거리가 된다.

---

5. BFS에서 들었던 또 다른 의문

BFS 풀이를 보다가 이런 의문이 들었다.

이동할 때마다 카운트를 증가시키면
나중에 돌아서 다시 오면 값이 꼬이지 않을까?

하지만 BFS에서는 이 문제가 발생하지 않는다.

이유는 방문 체크 때문이다.

BFS에서는

처음 방문한 순간

에만 거리 값을 기록한다.

그리고 같은 위치는 다시 방문하지 않는다.

즉

dist[next] = dist[current] + 1

이 값은 한 번만 기록된다.

그래서 값이 덮어쓰여서 꼬일 일이 없다.

---

6. BFS 상태 정의

이 문제에서 BFS의 상태는 단순하다.

현재 위치 x

즉

state = x

다음 상태는

x-1
x+1
2x

이다.

---

7. 방문 배열 설계

문제에서 위치 범위는

0 ≤ x ≤ 100000

이다.

따라서 방문 배열은 다음처럼 만들 수 있다.

visited[100001]

또는 거리까지 함께 저장하면

dist[100001]

이 된다.

---

8. BFS 설계

BFS 구조는 다음과 같다.

queue 생성
시작점 push
while queue:
    현재 위치 pop
    다음 위치 생성
    방문 안 했으면 queue push

이 문제에 적용하면

현재 위치 x

다음 위치
- x-1
- x+1
- 2x

이다.

---

 

---

2️⃣ 그래프로 생각하면 문제 구조가 보인다

숫자 → 노드
이동 → 간선

---

3️⃣ BFS의 핵심 성질

처음 도착한 순간 = 최단거리

---

마무리

숨바꼭질 문제는 단순한 BFS 문제처럼 보이지만
다음 개념을 이해하는 데 중요한 문제였다.

그래프 최단거리
BFS 탐색
방문 처리

이 문제를 통해 “최단거리 문제 → BFS”라는 판단 기준을 확실하게 잡을 수 있었다.