[Python]DFS와BFS 백준 1697

   문제

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

이 문제 역시 BFS를 사용하여 풀수있다.

정답률과 다르게 매우 쉬운문제이다.

DP문제와 유사해보이지만 이전값들을 사용하는 문제가 아니다. 계속 이동해가며 

찾아가면된다. 100000을 넘어서 이동한값들은 생각할 필요가없다.

from collections import deque
 
 
N,K=map(int,input().split())
check=[0 for _ in range(100001)]
 
q=deque()
q.append(N)
check[N]=1
while q:
    x=q.popleft()
    if x==K:
        time=check[x]-1
        break
    if x+1<=100000 and check[x+1]==0:#x+1로 걷기
        check[x+1]=check[x]+1
        q.append(x+1)
    if x-1>=0 and check[x-1]==0:#x-1로 걷기
        check[x-1]=check[x]+1
        q.append(x-1)
    if x*2<=100000 and check[2*x]==0:#순간이동
        check[x*2]=check[x]+1
        q.append(x*2)
 
 
print(time)

최적화를 해보자.

먼저 N>=K일때는 뒤로 한칸씩 걸어가는수밖에 없다. 이부분은 이렇게 N-K를 출력해 

주어도 될거같다.K>N일때만 bfs를 이용해 구해주면 될거같은데 메모리를 잡는데 굳이 

100000을 최대값을 잡을필요가없을거같다.그렇게 100000대신 K로 수정하여 제출하면 

틀리게되는데 그이유는  4 7을 넣어보면 알수있다.4->5->6->7 보다 4->8->7이 더빠르다.

 도착지가 홀수일 경우 이같은 일이 발생하는걸 알수있다.

K+1로 잡아주면 이 부분이 해결되고 맞았다는 결과를 볼수있다.

from collections import deque
 
N,K=map(int,input().split())
if N>=K:
    print(N-K)
else:
    check=[0 for _ in range(K+2)]
 
    q=deque()
    q.append(N)
    check[N]=1
    while q:
        x=q.popleft()
        if x==K:
            time=check[x]-1
            break
        if x+1<=K+1 and check[x+1]==0:#x+1로 걷기
            check[x+1]=check[x]+1
            q.append(x+1)
        if x-1>=0 and check[x-1]==0:
            check[x-1]=check[x]+1
            q.append(x-1)
        if x*2<=K+1 and check[2*x]==0:
            check[x*2]=check[x]+1
            q.append(x*2)
 
    print(time)