1697 숨바꼭질 / DFS, BFS

 

정답

• 일자로 이어진 그래프에서 최단 경로를 찾는다고 생각하면 됨 
• 최단 경로 == BFS

from collections import deque
n, k = map(int, input().split())

def BFS(n, k):
    # 최대 점의 길이 + 1 (리스트는 0부터 시작하므로)
    max_value = 100001
    # 방문을 체크할 리스트
    visited = [False] * max_value
    # 최초 시작지점 (수빈이의 위치)부터의 거리를 담는 리스트
    distance = [0] * max_value
    queue = deque()
    queue.append(n)
    visited[n] = True

    while queue:
        current = queue.popleft()

        # 현재 위치가 동생의 지점이라면, 수빈이의 지점부터 동생의 지점까지의 거리 반환
        if current == k:
            return distance[current]

        # 현재 위치가 동생의 지점이 아니라면, 수빈이가 갈 수 있는 경우의 수 걷기, 뛰기를 적용하여 조건에 부합한다면 큐에 넣기
        for next in (current - 1, current + 1, current * 2):
            # 0이상, 100000이하이고 방문하지 않았다면
            if next >= 0 and next < max_value and not visited[next]:
                queue.append(next)
                visited[next] = True
                distance[next] = distance[current] + 1

print(BFS(n, k))