[Backjoon] 1697 숨바꼭질 Python 문제 풀이

출처 : 숨바꼭질

문제해석

BFS를 탐색을 통해서 큐에 들어갈 분기를 세가지로 나눈다.

현재좌표+1, 현재좌표-1, 현재좌표*2

다음좌표가 경계체크를 벗어나지 않고 한번도 방문한적이 없다면 이전좌표까지의 방문시간+1을 다음좌표까지의 방문시간에 갱신한다.

현재좌표가 K가 될때까지 걸리는 시간의 최적해를 구한다.

해답코드

#숨바꼭질
from collections import deque

n, k = map(int, input().split())
MAX = 10 ** 5
isVisited = [0] * (MAX+1)

def bfs(startX):
    q = deque()
    q.append(startX)
    while q:
        x = q.popleft()
        if x==k:
            return isVisited[x]
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not isVisited[nx]:
                isVisited[nx] = isVisited[x]+1
                q.append(nx)
print(bfs(n))