[백준]12851 - 숨바꼭질2(python)

백준 12851 - 숨바꼭질

✔BFS를 이용하여 전체 visited와 ways를 체크하여 풀었습니다
처음에는 abs를 사용하여 현재 값과 목표 값의 차가 작아지는 방향으로 코드를 짰으나 그렇게 하면 빠지는 경우가 생겨 전체 경로를 탐색하는 방향으로 틀었음
ex) N,K = 5,17인 경우 N이 5 4 8 16 17로 변하는 경우가 최소 cnt

from collections import deque
N, K = map(int,input().split())#수빈, 동생

def cal(N,K):
    q = deque()
    q.append(N)

    max_limit = 100001
    visited = [0]*max_limit
    ways = [0]*max_limit
    visited[N] = 1
    ways[N]= 1

    while q:
        cur = q.popleft()
        for next_cur in (cur-1, cur+1, cur*2):
            if 0<= next_cur < max_limit:
                if not visited[next_cur]:
                    visited[next_cur] = visited[cur]+1
                    ways[next_cur] = ways[cur]
                    q.append(next_cur)
                elif visited[next_cur] == visited[cur]+1:
                    ways[next_cur] += ways[cur]
    return visited[K]-1, ways[K]



time,way = cal(N,K)
print(time)
print(way)