[백준_12761]_돌다리_python

https://www.acmicpc.net/problem/12761

12761번: 돌다리

문제

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

입력

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

출력

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

문제 해결

시작점 start에서 finish로 가기 위한 이동 횟수의 최솟값을 구하는 문제이다. now(시작점)에서 next(다음 도착지)로 가는 이동거리는

정해져 있기 때문에 visited로 +1 증가하는 식으로 True 체크하여 next와 finish가 일치하는 지점에 왔을 때의 이동 횟수인

visited의 max값(초기값 방문 체크를 위해 1부터 시작하여 출력 시 -1을 해준다)을 출력해주면 된다.

from collections import deque
a, b, start, finish = map(int,input().split())
visited = [0 for _ in range(100001)]
def dist(now,i):    #0~9
    global a,b
    arr = [now+1,now-1,now*a,-now*a,now*b,-now*b,now+a,now-a,now+b,now-b]
    return arr[i]

def bfs(start):
    global finish
    que = deque()
    que.append(start)
    visited[start]=1
    while que:
        node = que.popleft()
        for i in range(10):
            next = dist(node,i)
            if 0<=next<100001 and not visited[next]:
                visited[next] = visited[node]+1
                que.append(next)
                if next == finish:
                    return
bfs(start)
print(max(visited)-1)