티스토리 뷰

코딩/파이썬 백준

백준 12761 돌다리 (파이썬)

박상어 2022. 2. 1. 16:03
728x90

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

 

12761번: 돌다리

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import deque
 
 
def bfs(n):
    dq = deque([n])
    while dq:
        n = dq.popleft()
        visit[n] = True
        for i in range(len(direction)):
            if i < 6:
                nx = n + direction[i]
                if 0 <= nx < 100001 and not visit[nx]:
                    dq.append(nx)
                    lst[nx] = lst[n] + 1
                    visit[nx] = True
            else:
                nx = n * direction[i]
                if 0 <= nx < 100001 and not visit[nx]:
                    dq.append(nx)
                    lst[nx] = lst[n] + 1
                    visit[nx] = True
 
 
A, B, N, M = map(int, input().split())
lst = [0 for _ in range(100001)]
visit = [False for _ in range(100001)]
direction = [1, -1, A, B, -A, -B, A, B]
bfs(N)
print(lst[M])
 cs

 

'코딩 > 파이썬 백준' 카테고리의 다른 글

백준 16120 PPAP (파이썬)  (0) 2022.02.01
백준 1697 숨바꼭질 (파이썬)  (0) 2022.02.01
백준 13413 오셀로 재배치(파이썬)  (0) 2022.01.30
백준 16171 나는 친구가 적다 (파이썬)  (0) 2022.01.30
백준 2870 수학숙제 (파이썬)  (0) 2022.01.29
댓글