백준 1679 - 숨바꼭질

5 17

걷기 +- 1
순간이동 2*X
가장 빠른 시간?

5-10-9-18-17 5회

접근 방법이 안 떠오름
일단 따라가봐라

5
-> 4 6 10
-> 3 8 / 7 12 / 9 11 20 (이미 방문한 번호는 제외됨 (visited))
-> 2 / 16 / 14 / 13 24 / 18 22 / 19 21 40
-> 1 3 / 15 17 (탐색 종료)

BFS
visited = [] 문제 조건 따라 20만개로 설정

BFS 공략

• Queue, Visited
• 초기 노드 넣기
• current node = q.pop()
• 방향 넣기
• 범위조절
• next node = q.append(nn) (미방문시)

수도코드
bfs(s,e):
	[1] q생성, v생성
    [2] q.append(s) v[s] = 1
    [3] while q:
     		c= q.pop(0)
            # pop했는데 답이야 출력하고 종료
            # 3방향 => [c-1, c+1, c*2]
            # 범위 내 0 <= n <= 200000
            	q.append(next)
                visited[n] = visited[c] + 1 # 깊이 더하기

전체코드
import sys
from collections import deque
input = sys.stdin.readline


def bfs(s, e):
    global visited
    q = deque()
    q.append(s)
    visited[s] = 1
    while q:
        cn = q.popleft()
        if cn == e:
            return visited[cn]-1
        for n in (cn-1, cn+1, cn*2):
            if 0 <= n <= 200000 and visited[n] == 0:
                q.append(n)
                visited[n] = visited[cn] + 1


N, K = map(int, input().split())
visited = [0]*200001
print(bfs(N, K))