백준[16796]

step 0:1차원배열이니까 그리디의 top

step 1:그렇다면 브루트 포스 문제인가? X(시간초과)

step 2:다익스트라 알고리즘인가? X

step 3:예전에 BFS는 같은 거리비용(여기서는 한번 이동하는데 드는 비용이 1초로 똑같다) 문제에서 최단거리를 찾을 때 사용할 수 있다는 것을 본 적이 있다.

step 4:비록 1차원배열이지만 X+1   X-1   2*X 연산을 돌려가며 도착하지 않은 곳을 탐색해 가는 것이 가능하다.

step 5:부모 노드의 값+1을 해감으로써 초를 카운트

from collections import deque
N,K=map(int,input().split())
def bfs():
    q=deque()
    q.append(N)
    while q:
        loc=q.popleft()
        if loc==K:
            print(visited[loc])
            return
        for i in (loc-1,loc+1,2*loc):
            if 0<=i<Max and not visited[i]:
                q.append(i)
                visited[i]=visited[loc]+1
Max = 10 ** 5 + 1
visited = [0] * Max
bfs()

색칠한곳은 도착한곳 1은 2와3을 가지고있지만 방문처리가되서 더이상 탐색X 예를들어서 설명한것이니 문제와는 상관없다.

(처음 노드의 카운트값이 0이어서 다시 처음노드를 부르긴 하지만 그렇다고 계산에 방해가 되진 않는다.)