Notice
Recent Posts
Recent Comments
«   2024/11   »
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 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[BFS] 숨바꼭질 본문

프로그래밍

[BFS] 숨바꼭질

yesungcho 2024. 3. 24. 18:40

기억하자. 가중치가 없는 최단 경로는 무조건 BFS

가중치가 있는 경우 다익스트라

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

 

1697번: 숨바꼭질

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

www.acmicpc.net

 

여느 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])