[Boj] 숨바꼭질 1697(python)

문제링크 : https://www.acmicpc.net/problem/1697

시작 지점 N과 목표 지점 X가 주어지며, 목표지점을 최소한의 시간으로 도착하는 문제

따라서, BFS로 접근함. visited 배열을 이용하여 이미 간 인덱스는 다시 가지 못하게 막았으며

종료조건은 X에 도달한 경우임

단, 필자는 문제를 잘못 읽어서 0과 100000으로 이동할 수 없다고 생각하여 51%에서 실패했었음

문제를 다시 읽으니, 위 조건에 맞게 부등호를 조정하여 통과

문제의 범위는 항상 체크할 필요가 있음

from collections import deque

def BFS():

    while positions:
        start_position, time = positions.popleft()
        visited[start_position] = True

        if start_position == X:
            return time
        if start_position + 1 < 100001 and not visited[start_position + 1]:
            positions.append([start_position+1, time+1])
            visited[start_position + 1] = True
            if start_position + 1 == X:
                return time + 1
        if start_position - 1 >= 0 and not visited[start_position - 1]:
            positions.append([start_position - 1, time + 1])
            visited[start_position - 1] = True
            if start_position - 1 == X:
                return time + 1
        if start_position * 2 < 100001 and not visited[start_position * 2]:
            positions.append([start_position * 2, time + 1])
            visited[start_position * 2] = True
            if start_position * 2 == X:
                return time + 1

N, X = map(int, input().split())
positions = deque()
positions.append([N, 0])
visited = [False] * 100001
print(BFS())