[백준] #13549. 숨바꼭질 3 (파이썬/Python)

 

📖 문제

[백준] #13549. 숨바꼭질 3 (파이썬/Python)

• 난이도: 골드5
• 유형: BFS

문제 요약

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

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

• `X - 1` (1초 소요)
• `X + 1` (1초 소요)
• `2 * X` (0초 소요)

목표는 동생에게 도달하는 데 걸리는 최소 시간(초)을 구하는 것이다.

(숨바꼭질 시리즈)

---

🔍 문제 접근

💡 문제 분석

처음에 틀린 이유를 찾을 수가 없어서 GPT의 도움을 받았다.

이 문제는 가중치가 0 또는 1인 그래프에서의 최단 거리 문제이다.

• `X → 2X`는 이동 시간 0 → 가중치 0
• `X → X±1`은 이동 시간 1 → 가중치 1

이처럼 간선 가중치가 0 또는 1일 경우, 일반 BFS가 아닌 0-1 BFS 기법을 사용해야 한다.

 

🚀 0-1 BFS란?

0-1 BFS는 간선 가중치가 0 또는 1인 그래프에서 최단 경로를 빠르게 구하는 알고리즘이다.

일반적인 BFS와 유사하지만, 다음과 같은 특징이 있다:

	0-1 BFS	다익스트라 (heapq)
간선 가중치	0 또는 1만 허용	양의 정수 아무 값
사용 자료구조	deque	우선순위 큐 (heapq)
시간 복잡도	O(V + E)	O((V + E) log V)
처리 속도	더 빠름	비교적 느림

작동방식

• 가중치가 0이면 `appendleft()`를 사용하여 큐의 앞쪽에 넣는다.
  • → 즉시 처리하여 빠르게 탐색한다.
• 가중치가 1이면 `append()`를 사용하여 큐의 뒤쪽에 넣는다.
  • → 하나의 시간 단위가 지난 후 처리된다.

이렇게 하면 별도의 우선순위 큐 없이도, 가중치에 따라 탐색 순서가 자동으로 조절된다

 

🧠 풀이 아이디어

BFS 로직은 다음과 같다.

• 시작점 `N`부터 BFS 탐색을 진행한다.
• `visited[x]`에는 `x` 위치에 도달하는 데 걸린 최소 시간을 저장한다.
• 큐를 탐색하며 큐에 있는 값을 `current`에 저장한다.
• 순간이동 (`current * 2`)는 0초로, 우선적으로 탐색되어야 한다. 따라서 `current * 2`를 먼저 처리하고, `appendleft()`로 처리한다.
  • 범위 내에 있고 방문한 적이 없을 경우 `current * 2` 위치까지 걸린 시간은 `current`와 동일하다.
  • 큐에 추가한다. (`appendleft`)
• 걷기 (`current + 1`, `current - 1`)는 1초 걸리므로 `append()`로 추가한다.
  • 범위 내에 있고 방문한 적이 없을 경우 `current * 2` 위치까지 걸린 시간은 `current`에 1을 더한 값이다.
  • 큐에 추가한다. (`append`)
• 탐색 중에 `K`에 도달하면 최소 시간이므로 바로 종료한다.

 

---

🔍 문제 풀이

♻️ 코드 플로우

1. 최대 좌표값인 `100000`까지 탐색할 수 있도록 범위 상수를 선언한다.
2. `visited` 리스트를 `1`로 초기화하여 방문 여부와 시간을 동시에 기록한다.
3. `deque`를 생성하고 시작 위치를 넣는다.
4. 다음 규칙에 따라 큐를 순회하며 위치를 탐색한다:
   • `2 * x` (순간이동): `appendleft()`, 시간 변화 없음
   • `x ± 1 `(걷기): `append()`, 시간 +1
5. 목표 위치 K에 도달하면 종료한다.

🚩 제출한 소스 코드

import sys
from collections import deque
input = sys.stdin.readline

MAX = 100000
N, K = map(int, input().split())
visited = [-1] * (MAX + 1)

queue = deque()
queue.append(N)
visited[N] = 0

while queue:
    current = queue.popleft()

    # 순간이동 (0초) -> 큐 앞쪽에 넣기
    nx = current * 2
    if 0 <= nx <= MAX and visited[nx] == -1:
        visited[nx] = visited[current]
        queue.appendleft(nx)  # 핵심!

    # 걷는 경우 (+1, -1) -> 큐 뒤쪽에 넣기
    for nx in (current - 1, current + 1):
        if 0 <= nx <= MAX and visited[nx] == -1:
            visited[nx] = visited[current] + 1
            queue.append(nx)

print(visited[K])

• 틀렸던 이유
  • 문제의 핵심은 아래와 같다.
    • 2로 순간이동하는 경우는 시간이 0초.
    • +1, 1로 걷는 경우는 시간이 1초.
  • 이 경우에는 가중치가 0 또는 1인 그래프 → 0-1 BFS 필요하다.
  • 하지만 틀린 풀이에서는 가중치에 다라 처리하지 않았다.
    • 0초 걸리는 이동 (2)는 앞쪽에 appendleft() 해야 하고,
    • 1초 걸리는 이동 (+1, 1)은 뒤쪽에 append() 해야 최단 경로를 제대로 탐색할 수 있다.

🚩 다른 분의 풀이

[백준] 13549. 숨바꼭질3 (파이썬)

import heapq
INF = int(1e9)

N, K = map(int, input().split())
distance = [INF] * 100001

def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for n in (now+1, now-1, now*2):
            if n < 0 or n > 100000:
                continue

            cost = dist
            if n != now*2:
                cost = dist + 1

            if cost < distance[n]:
                distance[n] = cost
                q.append((cost, n))

dijkstra(N)
print(distance[K])

---

💡회고

• 이 문제가 숨바꼭질2와 다른 점은 “0초 이동”을 처리해야 한다는 것이다. 숨바꼭질2와 비슷하게 풀면 정확할 수 없다.
• 이 문제를 통해서 0-1 BFS 유형을 알게 되었다. `0-1 BFS`를 구현하기 위해서는 우선순위가 높은 것은 (deque 기준으로) `appendleft`로 우선 탐색할 수 있도록 해주어야 한다는 것을 알게 되었다.
• `heapq`로도 풀이 가능하다.