[python] 백준 12761번 돌다리

문제

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

풀이

갈 수 있는 방법을 리스트에 넣어두고, 각 방법을 모두 진행하면서 도착하는 돌의 번호까지의 이동횟수에 ,
이전 이전 돌까지의 이동횟수 +1 을 해주면 된다.
 
우선 갈 수 있는 방법은
1, -1, a, -a, b, -b, *a, *b 이다.
 
해당 방법대로 맨처음 돌번호에 차례대로 진행시켜보자.
처음 예제 대로 N, M, A, B가 각각 1, 20, 2, 3이라고 가정하자
시작 돌번호(N)이 1이라고 할때, 
1 + 1 = 2
1 - 1 = 0
1 + 2 = 3
1 + 3 = 4
1 - 2 = - 1 (x)
1 - 3 = -2 (x)
1*2 = 2
1*3 = 3
 
갈 수 있는 경우의 수는 이렇게 8가지 이다. 
큐에 [2,0,3,4] 순으로 값을 넣어주고, 이 큐는 1 이후 방문 할 돌번호의 순서가 될 것이다. 
 
모든 돌번호까지의 이동횟수를 0으로 초기화 하고,
1에서 한번만 움직여서 갈 수 있는칸에 +1 해서 넣어준다.

[인덱스] 0	1	2	3	4	5	6	...
[이동횟수] 1	0	1	1	1	0	0	...

위와 같이 2번 3번 4번 돌은 한번만에 갈 수 있는 것이다.
 
그리고 이어서, 2번에서 이동할 수 있는 돌번호에 동일하게 진행을 해준다.
단, 이미 방문했던 번호는 방문하지 않는다.
또, 큐에 방문 순서를 기록하며 순서대로 이동할 수 있는 횟수를 카운팅 해주면 된다.
bfs 방식으로 가장 먼저 들어왔던 2를 진행하며, 2에서 추가로 더 갈 수 있는 돌의 번호에 이동횟수를 +1 시켜준다.
 

[인덱스] 0	1	2	3	4	5	6	7	...
[이동횟수] 1	0	1	1	1	2	2	0	...

 
이런식으로 해당 리스트를 큐가 남아있지 않을 때까지 반복하면,
모든 번호의 최소 이동 횟수를 구할 수 있다.
 
도착할 번호의 인덱스 값이 해당 번호까지 가는 최소 이동 횟수이다.
 

정답 

import sys
from collections import deque

input = sys.stdin.readline

a,b,n,m = map(int, input().split())
visited = [False for _ in range(100001)]
graph = [0 for _ in range(100001)]
def bfs(x):
    pos = [1,-1,a,-a,b,-b,a,b]
    visited[x] = True
    queue = deque([x])    
    
    while queue:
        v = queue.popleft()
        for i in range(8):
            if i<6:
                y = v + pos[i]
                
            else:
                y = v * pos[i]
            
             
            if 0<=y<=100000 and visited[y] == False:
                visited[y] = True
                queue.append(y)
                graph[y] = graph[v] + 1 
            
    
bfs(n)
print(graph[m])