boj 1697

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

from sys import stdin
from collections import deque
N, K = map(int, stdin.readline().split())
count = 0
roads = deque([[N, count]])
visited = [False] * 100001

while roads:
    sc = roads.popleft()
    start = sc[0]
    count = sc[1]
    if visited[start] == False:
        visited[start] = True
        if start == K:
            print(count)
            break
        count += 1
        if start + 1 <= 100000:
            roads.append([start+1,count])
        if start - 1 >= 0:
            roads.append([start-1,count])
        if start * 2 <= 100000:
            roads.append([start * 2,count])

notion

• 언니가 동생과 숨바꼭질 하는 게임
• 일차원 평면에서 게임하는 상황에서 bfs 를 사용한다.
• 탐색하는 경우에는 bfs를 사용한다고 생각하면 된다.
• count를 언제 하냐가 가장 중요했던 문제.
• 하나의 노드에서 텀색할때 count를 같이 append 해줌으로써 기억하게 한다.