Python/DFS BOJ-13549 숨바꼭질 3

Posted on | In

[Python/DFS] BOJ-13549 숨바꼭질 3

📌문제링크 풀이참고

*풀이참고 링크에 들어가서 보시면 됩니다.

동생위치에 갈수있는 최단시간을 구하는 문제다.
걷거나 순간이동을 할 수 있는데, 이때 순간이동의 경우 0초가 소모되므로 우선순위를 가지도록 appendleft를 활용하면된다.

BFS solution

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
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

if __name__ == '__main__':
    n,k = map(int,input().split())
    queue = deque([n])
    MAX_v = 100001
    visited = [False]*MAX_v
    time = [0]*MAX_v
    visited[n] = True
    while queue:
        s = queue.popleft()
        if s == k :
            break
        if 0 <= 2*s < MAX_v and not visited[2*s] :
            visited[2*s] = True 
            time[2*s] = time[s]
            queue.appendleft(2*s)
        if 0 <= s+1 < MAX_v and not visited[s+1] :
            visited[s+1] = True 
            time[s+1] = time[s]+1
            queue.append(s+1)
        if 0 <= s-1 < MAX_v and not visited[s-1] :
            visited[s-1] = True 
            time[s-1] = time[s]+1
            queue.append(s-1)
    print(time[s])