[BOJ] 12761 돌다리 (Pytyon3)

문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 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≤A,B≤30이고 0≤N,M≤100,000)

출력

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

예제 입력 1  
2 3 1 20
예제 출력 1  
4


예제 입력 2  
3 7 2 98500
예제 출력 2  
10

풀이

좌우좌표계로 연결된 노드로 생각하고 bfs를 사용하여 방문한적이 없다면 점프하기 전의 위치에서 1을 더한값을 현재위치에 저장해 주며 앞으로 끝까지 나아간다. 그 이후에 주미가 있는 곳의 숫자를 출력해주면, 그 숫자가 동규가 주미에게 도달하기위한 최소 이동 횟수가 된다.

코드

from collections import deque
def bfs(x):
    visited[x] = 1
    q = deque()
    q.append(x)
    while q:
        nx = q.popleft()
        for i in range(8):
            if i < 6:
                sx = nx+dx[i]
                if 0 <= sx <= 100000 and visited[sx] == 0:
                    q.append(sx)
                    visited[sx] = 1
                    stone[sx] = stone[nx]+1
                
            else:
                sx = nx*dx[i]
                if 0 <= sx <= 100000 and visited[sx] == 0:
                    q.append(sx)
                    visited[sx] = 1
                    stone[sx] = stone[nx]+1
                
        
A,B,N,M = map(int, input().split())

stone = [0 for i in range(100001)]
visited = [0 for i in range(100001)]

dx =[1,-1,A,-A,B,-B,A,B]

bfs(N)

print(stone[M])

2 3 1 20
4