백준 12761번

돌다리

시간 제한 : 1 초 메모리 제한 : 128 MB

문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 (N)번 돌 위에, 주미는 (M)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 (A, B) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 (A)나 (B)만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 (A)배나 (B)배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

입력의 첫 줄에 스카이 콩콩의 힘 (A)와 (B), 그리고 동규의 현재위치 (N), 주미의 현재 위치 (M)이 주어진다. (단, (2 \le A, B \le 30) 이고
(0 \le N, M \le 100,000))

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라

해설

이 문제는 동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 구하는 문제입니다. 주어진 이동 방법들 중에서 최적의 방법을 선택하여 최소 횟수로 동규가 주미에게 도달할 수 있어야 합니다.

주어진 코드는 너비 우선 탐색(BFS)을 이용하여 문제를 해결하고 있습니다. BFS를 사용하는 이유는 최소 이동 횟수를 구하기 위함입니다. BFS는 시작 노드로부터 가장 가까운 노드부터 방문하기 때문에, 주미에게 도달하면 그때의 이동 횟수가 최소 횟수가 됩니다.

해결 방법은 다음과 같습니다:

1. 큐 초기화: BFS를 수행하기 위한 큐를 초기화하고, 동규의 현재 위치와 이동 횟수 0을 큐에 넣습니다.
2. 방문 기록: 방문한 위치를 기록하기 위한 집합 visited를 사용합니다. 동규의 현재 위치를 visited에 추가합니다.
3. BFS 수행: 큐가 빌 때까지 BFS를 수행합니다. 현재 위치와 이동 횟수를 큐에서 꺼냅니다. 현재 위치가 주미의 위치와 같다면, 현재의 이동 횟수를 반환합니다. 현재 위치에서 가능한 모든 이동 방법을 사용하여 다음 위치를 구합니다. 다음 위치가 유효하고(0~100,000 사이) 아직 방문하지 않았다면, visited에 추가하고 큐에 넣습니다.
4. 결과 출력: BFS를 통해 구한 최소 이동 횟수를 출력합니다. 이 코드는 BFS를 통해 모든 가능한 이동 경로를 탐색하며, 주미에게 도달하는 최소 이동 횟수를 구합니다.

from collections import deque

def BFS(a,b,n,m):
    queue = deque([(n, 0)])
    visited = set([n])

    while queue:
        x, time = queue.popleft()

        if x == m:
            return time
        
        for nx in [x-1, x+1, x+a, x-a, x+b, x-b, x*a, x*b]:
            if 0 <= nx <= 100000 and nx not in visited:
                visited.add(nx)
                queue.append((nx, time+1))

a,b,n,m=map(int,input().split())
print(BFS(a,b,n,m))