[Python] BOJ 12761 - 돌다리

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

12761번: 돌다리

# "현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다."

 -> 동규가 이동할 수 있는 경우의 수는 다음과 같다. (현재 동규위치: x)

     (x+1, x-1, x+A, x-A, x+B, x-B, x*A, x*B, x*(-A), x*(-B))

 

# 마지막 두개 케이스 x*(-A)와 x*(-B) 는 무조건 주미로부터 멀어지기 때문에 제외하고 나머지

  8개 케이스만 확인하면 된다.

 

# "숨바꼭질"문제와 비슷하게 진행하면 된다.

  BFS를 돌려서 8개 케이스를 확인하면서 i가 100000이하이거나 이미 방문하지 않은 돌일때 

  cnt[i] = cnt[x] + 1을 해준다.

 

# 중간에 M번째 돌에 도달했으면 cnt[x] + 1을 출력하고 종료하고

   아니면 마지막에 cnt[M]으로 M번째 돌까지 가는데 필요한 최소횟수를 출력해준다.

 

import sys
from collections import deque
A, B, N, M = map(int,input().split())
visited = [False] * 100001
cnt = [0] * 100001
q = deque()
def bfs(N):
	q.append(N)
	while q:
		x = q.popleft()
		for i in (x+A, x+B, x*A, x*B, x-A, x-B, x+1, x-1):
			if i == M:
				print(cnt[x] + 1)
				sys.exit(0)
			if 0 <= i < 100001 and not visited[i]:
				cnt[i] = cnt[x] + 1
				visited[i] = True
				q.append(i)
bfs(N)
print(cnt[M])

(solved.ac 티어: 실버 2)