[Python/파이썬] 백준 13549 - 숨바꼭질3

문제 설명

 

입출력 예제

 

---

풀이 코드

1. 동생의 위치 k에 도달할 때 까지 문제에 주어진 3가지 이동방법으로 탐색한다.
2. 문제에 주어진 범위 0 <= N <= 100,000안 일 경우 탐색하도록 한다.
3. 순간이동을 많이 쓰는 방법이 가장 빠르게 도착하는 방법으로 순간이동은 appendleft()로 먼저 탐색하도록 한다.
4. 동생의 위치 k에 도달하면 도착 시작 값을 반환한다.

정답 코드

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

n, k = map(int, input().split()) # 수빈이의 위치, 동생의 위치

def bfs():
    visited = [-1] * 100001
    visited[n] = 0
    q = deque([n])

    while q:
        cur = q.popleft()

        # 동생의 위치에 도달하면 값 반환
        if cur == k:
            return visited[cur]

        # 동생의 위치에 도달할 때 까지, 3가지의 이동 경우를 확인 (x + 1, x - 1, x * 2)
        for next in (cur + 1, cur - 1, cur * 2):
            if 0 <= next <= 100000 and visited[next] == -1:
                if next == cur * 2:
                    visited[next] = visited[cur] # 순간이동은 0초 소요
                    q.appendleft(next) # appendleft()로 순간이동을 먼저 탐색
                else:
                    visited[next] = visited[cur] + 1 # 걸어서 이동은 1초 소요
                    q.append(next)

print(bfs())