[알고리즘/백준] 13549번 : 숨바꼭질 3(python)

처음에 시간이 다 1이 느는줄 알았다... 하지만 나중에 보니 순간이동은 시간이 늘지 않았다.
가중치가 0, 1로 이루어져 있으면 0-1bfs를 사용하면 된다.

만약 가중치가 여러개면 다익스트라를 사용

가중치가 0인 계산이 들어오면 appendleft를 이용해서 큐 맨 앞에 추가시켜 준다.

참고

from collections import deque


def bfs(now, time):
    q = deque()
    q.append([now, time])
    while q:
        n, t = q.popleft()
        if n == K:
            print(t)
            break
        for nx in (n * 2, n + 1, n - 1):
            if nx / 2 == n:
                if 0 <= nx <= 100000 and visited[nx]:
                    visited[nx] = 0
                    q.appendleft([nx, t])
            else:
                if 0 <= nx <= 100000 and visited[nx]:
                    visited[nx] = 0
                    q.append([nx, t + 1])


N, K = map(int, input().split())
visited = [1] * 100001
bfs(N, 0)