티스토리 뷰

코딩/파이썬 백준

백준 1697 숨바꼭질 (파이썬)

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

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

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()
        direction = [-1, 1, 2]
        visit[n] = True
        for i in range(len(direction)):
            if i < 2:
                idx = direction[i] + n
                if 0 <= idx < 100001 and not visit[idx]:
                    dq.append(idx)
                    lst[idx] = lst[n] + 1
                    visit[idx] = True
            else:
                idx = direction[i] * n
                if 0 <= idx < 100001 and not visit[idx]:
                    dq.append(idx)
                    lst[idx] = lst[n] + 1
                    visit[idx] = True
 
 
N, K = map(int, input().split())
lst = [0 for _ in range(100001)]
visit = [False for _ in range(100001)]
bfs(N)
print(lst[K])
 cs

 

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

백준 1743 음식물 피하기 (파이썬)  (0) 2022.02.02
백준 16120 PPAP (파이썬)  (0) 2022.02.01
백준 12761 돌다리 (파이썬)  (0) 2022.02.01
백준 13413 오셀로 재배치(파이썬)  (0) 2022.01.30
백준 16171 나는 친구가 적다 (파이썬)  (0) 2022.01.30
댓글