백준 1697번 숨바꼭질

https://www.acmicpc.net/problem/1697
실패이유 : 구현실패

import collections

MAX = 100000
soobin, younger = map(int, input().split())

distance = [0] * (MAX + 1)
visit = [False] * (MAX + 1)

visit[soobin] = True

queue = collections.deque([soobin])

while queue:
    current_location = queue.popleft()

    if current_location > 0:                                                    # 현재 위치에서 한 칸 뒤로
        if not visit[current_location - 1]:
            distance[current_location - 1] = distance[current_location] + 1
            visit[current_location - 1] = True
            queue.append(current_location - 1)

    if current_location < MAX:                                                  # 현재 위치에서 한 칸 앞으로
        if not visit[current_location + 1]:
            distance[current_location + 1] = distance[current_location] + 1
            visit[current_location + 1] = True
            queue.append(current_location + 1)

    if current_location * 2 <= MAX:                                             # 현재 위치에서 순간이동 (x2)
        if not visit[current_location * 2]:
            distance[current_location * 2] = distance[current_location] + 1
            visit[current_location * 2] = True
            queue.append(current_location * 2)

print(distance[younger])

• 그래프로 모델링하여 풀 수 있다.
  • 정점 : 위치
  • 간선 : 위치 - 위치
    
    각 위치로 이동하는 데 걸리는 시간 (가중치) 이 1로 모두 같다.
• BFS 를 사용하여 모든 위치를 이동하는 데 걸리는 시간을 구할 수 있다.

출처 : 코드플러스 - 알고리즘 기초 2/2 강의
https://code.plus/course/42