No Limitation
[BFS] 숨바꼭질 본문
기억하자. 가중치가 없는 최단 경로는 무조건 BFS
가중치가 있는 경우 다익스트라
https://www.acmicpc.net/problem/1697
여느 BFS 문제와 크게 다르지 않았음
from collections import deque
N, K = [int(x) for x in input().split()]
#M = max(N,K) ## 이걸로 하면 안되고 걍 100000 사용하자
visited = {i:0 for i in range(100000)}
queue = deque()
queue.append(N)
visited[N] = 0
while queue :
current = queue.popleft()
if current == K :
break
moving = [current+1,current-1,2*current,(-2)*current]
for i in range(4) :
new = moving[i]
if new < 0 or new > 100000 :
continue
if visited[new] == 0 :
queue.append(new)
visited[new] = visited[current] + 1
print(visited[K])
'프로그래밍' 카테고리의 다른 글
[BFS] 일자 기준에 따른 counting (0) | 2024.03.27 |
---|---|
[BFS] 동일 Set 유형 2 (0) | 2024.03.27 |
[다익스트라] heap을 사용한 다익스트라 예제 연습 (0) | 2024.03.22 |
[SQL] 주의해야 할 유형 (0) | 2024.03.21 |
[DFS] 모음사전 (0) | 2024.03.21 |