[백준-13549] 숨바꼭질 3 / Python

13549번: 숨바꼭질 3

from collections import deque

n, k = map(int, input().split())
graph = [0] * 100001

dx = [-1, 1, 2]


def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        x = queue.popleft()
        if x == k:
            print(graph[x])
            break
        for i in range(3):
            if i == 2:
                nx = x * dx[i]
            else:
                nx = x + dx[i]
            if 0 <= nx < 100001 and graph[nx] == 0:
                if nx == x * 2 and x != 0:
                    graph[nx] = graph[x]
                    queue.appendleft(nx)
                else:
                    graph[nx] = graph[x] + 1
                    queue.append(nx)


bfs(n)

 

해설

이전 실버에서 풀었던 숨바꼭질 문제와 비슷한 문제다. 다만 2*x만큼 이동할 때 소요되는 시간이 0초라는 부분에서 달랐다. 2*x만큼의 이동에 0초가 소요되므로 graph[x]와 같은 값으로 저장하고 deque에는 appendleft로 우선순위를 높여줘서 풀었다.😁