DP 문제풀이 - (1)

1697번 숨바꼭질

처음에는 백트래킹 문제인줄 알고 재귀함수를 이용해보려고 했는데 무한으로 되고 어떻게 막아야 할지 모르겠어서 실패했다.

이렇게 트리를 그려보니 17에서 리턴을 해줘도 오른쪽 노드로 순회하면서 빠져나오지 않았다.
트리를 그려보니 트리탐색 같았고 문제를 다시 읽어보니 가장 빠른 시간을 구한다고 해서 bfs 문제구나 싶었다.
그리고 바로 해결!
모든 노드를 다 순회한다고 할때 최대 100000번 반복하므로 0(10^5)

from collections import deque

N,K=map(int,input().split())
visited = [False for _ in range(100001)]

def bfs(n,k):
    q=deque()
    q.append((n,0))
    visited[n]=True
    while q:
        now,sec=q.popleft()
        if now==k:
            return sec
        if now -1 >=0 and not visited[now-1]:
            q.append((now-1,sec+1))
            visited[now-1]=True
        if now +1 <=100000 and not visited[now+1]:
            q.append((now+1,sec+1))
            visited[now + 1] = True
        if 2*now <=100000 and not visited[now*2]:
            q.append((now*2,sec+1))
            visited[now * 2] = True

print(bfs(N,K))