[BOJ] 백준 13913 숨바꼭질 4 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다.

이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다.

 

가장 빠른 시간을 구하고 경로를 출력해야한다.

현재 위치 바로 직전 번호를 따로 저장해두고, 역추적하며 문자열로 저장해 출력했다.

 

 

 

구현 언어: Python

 

from collections import deque


def solve():
    global n, k, sec, route
    queue = deque()
    # 시작점 세팅
    queue.append(n)
    sec[n] = 0
    route[n] = n

    while queue:
        now = queue.popleft()

        for next in (now - 1, now + 1, now * 2):
            if 0 <= next <= 100000:
                if sec[next] == -1:
                    sec[next] = sec[now] + 1
                    queue.append(next)
                    # 경로 저장
                    route[next] = now


n, k = map(int, input().split())
sec = [-1] * 100001  # 이동 시간 기록
route = [0] * 100001   # 경로 기록
answer = ''
solve()
print(sec[k])

while route[k] != k:
    answer = str(k) + ' ' + answer
    k = route[k]
answer = str(n) + ' ' + answer
print(answer[:-1])