[boj] 백준 13549 숨바꼭질 3 python 풀이(bfs)

문제

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

13549번: 숨바꼭질 3

 

문제 풀이

cost가 작은 순간이동을 우선으로 하여 bfs 돌림

 

코드 

import sys
input = sys.stdin.readline
import collections

N, K = map(int,input().split())

q = collections.deque()
q.append((N,0))
visited = [0 for _ in range(100001)]
visited[N] = 1

while q:
    cur_loc, time = q.popleft()
    if cur_loc == K:
        break

    for i in range(3):
        if i == 0:
            n_loc = cur_loc * 2
            n_time = time
        elif i == 1:
            n_loc = cur_loc -1
            n_time = time + 1
        else:
            n_loc = cur_loc+1
            n_time = time + 1

        if 0<=n_loc<=100000 and visited[n_loc] == 0:
            q.append((n_loc, n_time))
            visited[n_loc] = 1
            
print(time)