백준 / 숨바꼭질 / 1697

Question

문제링크
Silver 1

Logic

기본 구조 : bfs
1. N은 K가 되기 위해서 3갈래 경우의 수로 나뉜다.

2n, n-1, n+1

2. 나는 이 문제를 그래프의 관점에서 바라보았다. n에서 k까지 탐색하는 최단 거리의 그래프. 방법은 dfs와 bfs가 있다.
3. 하지만, n의 자식중에는 n-1과 n+1이 있으므로, dfs를 택하면 무한 루프에 빠진다.
4. 따라서, 방식은 bfs를 택하고, deque 대신 list와 pop(0)을 활용한다.
5. 시간을 단축하기 위해 visited는 dictionary로 구현한다.
6. 각 경우의 수에서 0미만, 100000초과, 방문한적이 있는 노드 일 경우 계산하지 않는다.

Code

from sys import stdin
from sys import stdin

n = 0
def bfs(n,k):
    visited={i:0 for i in range(100001)}
    queue = [(n,0)]
    while queue:
        n = queue.pop(0)
        num=n[0]
        if num == k : break
        if num<0 or num>100000 : continue
        if visited[num]==1 : continue
        visited[num]=1
        for nn in [num*2, num-1, num+1] : queue.append((nn,n[1]+1))
    return n[1]

N,K = map(int,stdin.readline().rstrip().split())
print(bfs(N,K))