백준
백준 12761 돌다리 (파이썬)
chldkato
2020. 2. 22. 14:31
https://www.acmicpc.net/problem/12761
12761번: 돌다리
동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 \(A, B\) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해
www.acmicpc.net
주어진 조건대로 구현하여 bfs를 진행하면 된다
단, 시작을 0부터하면 예제입력2 같은 경우에 오답이 나오기 때문에 1부터 시작해야한다
from collections import deque
import sys
input = sys.stdin.readline
def bfs():
q.append(n)
c[n] = 1
while q:
x = q.popleft()
if x == m:
print(c[x]-1)
for i in range(3):
nx = x + jump[i]
if nx < limit and not c[nx]:
c[nx] = c[x] + 1
q.append(nx)
nx = x - jump[i]
if nx > 0 and not c[nx]:
c[nx] = c[x] + 1
q.append(nx)
nx = x * jump[i]
if nx < limit and not c[nx]:
c[nx] = c[x] + 1
q.append(nx)
a, b, n, m = map(int, input().split())
jump = [1, a, b]
limit = 100001
c = [0 for _ in range(limit)]
q = deque()
bfs()