백준 13549번 - 숨바꼭질 3

숨바꼭질 3 문제 바로 가기

풀이 날짜: 2026-01-23

baekjoon 알고리즘 문제 풀이

풀이 코드


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

n,k = map(int, input().split())
MAX = 100000
road = [-1] * (MAX + 1)

queue = deque()
queue.append(n)
road[n] = 1

while queue:
    popN = queue.popleft()
    if popN == k:
        print(road[k]-1)
        break
    for newN in (2*popN, popN-1, popN+1):
        if not (0<=newN<=MAX):
            continue

        if road[newN] != -1:
            continue

        if newN == 2 * popN:
            road[newN] = road[popN]
            queue.appendleft(newN)
        else:
            road[newN] = road[popN] + 1
            queue.append(newN)

print(count)

문제 핵심 요약:

이 문제는 이동이 3가지인데, 그중 x → 2x는 시간이 0초, x → x±1은 1초가 든다. 즉 간선 비용이 모두 같은 BFS 문제가 아니라, 비용이 0과 1로 섞인 최단거리 문제다. 이 구조 때문에 단순 BFS(모든 간선 비용=1 가정)는 최단 시간을 보장하지 못하고, “0초 이동을 먼저 처리하는” 방식이 필요했다.

왜 0-1 BFS ?!

가중치가 0 또는 1만 존재하는 그래프에서 최단거리를 구할 때는 다익스트라보다 더 간단한 0-1 BFS를 사용할 수 있다. 핵심 아이디어는 “0초 이동은 우선 처리”하고 “1초 이동은 그 다음 처리”해서, 전체 탐색 순서를 시간 오름차순처럼 유지하는 것이다. 이를 위해 일반 큐가 아니라 deque(덱) 을 사용한다.

MAX와 road 배열을 쓰는 이유

좌표는 0~100000 범위 안에서만 의미가 있으므로 MAX=100000으로 탐색 공간을 제한했다. 그리고 road[x]는 “x 위치까지 도달하는 최소 시간(거리)”를 저장한다. 초기값을 -1로 두어 아직 방문하지 않은 상태를 명확하게 표시하고, 방문 여부 + 최단거리 값을 하나의 배열로 관리할 수 있게 했다.

시작 값을 road[n]=1로 둔 이유(출력에서 -1)

보통은 road[n]=0으로 시작하는데, 이 코드에서는 road[n]=1로 두고 나중에 road[k]-1을 출력하도록 했다. 즉 내부적으로는 시간을 1부터 카운트하고, 마지막에 0초 기준으로 되돌리는 방식이다.

appendleft와 append의 차이

0-1 BFS의 핵심은 비용 0 이동을 덱의 앞에 넣고(appendleft), 비용 1 이동은 덱의 뒤에 넣는(append) 것이다. 이렇게 하면 덱에서 popleft()로 꺼낼 때 항상 “현재까지 시간이 더 작은 상태”가 먼저 처리되는 효과가 생긴다.

이 코드에서 비용 0/1을 구분하는 부분

newN == 2*popN인 경우는 순간이동이므로 비용이 0이고, 이때는 road[newN] = road[popN]로 시간을 늘리지 않는다. 그리고 우선 처리해야 하므로 queue.appendleft(newN)를 사용한다. 반면 popN-1, popN+1은 비용 1이므로 road[newN] = road[popN] + 1로 갱신하고 덱 뒤에 append한다. 이 “비용에 따른 삽입 위치”가 최단거리 보장의 핵심이다.

종료 조건

탐색 중 popN == k가 되는 순간, road[k]에는 최소 시간이 기록되어 있다. 그래서 바로 출력하고 종료할 수 있다. 이 코드에서는 시작값을 1로 뒀기 때문에 최종 출력은 road[k]-1로 보정한다.

Vienna sausage