12852번 숨바꼭질 2

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

아이디어

최단 경로를 찾는 건 쉬웠는데 최단 경로로 k에 몇 번 도달했는지 카운트 하는 게 막혔었다.
그래서 생각한 것은 어차피 최단 경로로 도착하는건 처음 k에 도달했을 때이다. 그러므로 그 이후에도 아직 방문하지 않았거나 최단경로로 재방문일 경우에만 queue에 넣는다. 그리고 queue에서 pop 할 때 그 수가 k라면 카운트 해주면 된다. (k에 도착한 건 최단경로이기 때문)

코드

from collections import deque

def bfs(n):
    queue = deque([n])
    numbers = 0
    while queue:
        x = queue.popleft()
        if x == k:
            numbers += 1
        for nx in (x-1, x+1, x*2):
            if nx < 0 or nx >= MAX:
                continue
            if graph[nx] == -1 or graph[nx] == graph[x]+1: 
                graph[nx] = graph[x]+1
                queue.append(nx)
    return numbers

n, k = map(int, input().split())
MAX = 100001
graph = [-1]*MAX
graph[n] = 0 # 수빈이 시작 위치

a = bfs(n)
print(graph[k])
print(a)