[BaekJoon] 백준 알고리즘 1697번 / 숨바꼭질 / BFS / Python

 

"""
1. 아이디어
- x-1, x+1, 2x의 케이스를 나눠서 탐색한다.
- 해당 수에 이미 방문했다면 다시 방문하지 않는다.

2. 시간복잡도
- 좌표 200_000개
- 간선 200_000 * 3개 = 600_000개
- 800_000 < 2억개! 가능.

3. 자료구조
- q [] 
- visited []

4. 시나리오
    1) q [] 생성, v [] 생성 
    2) 초기 q.append(s), v[s] = 1
    3) while q:
    4)      c = g.pop(0)
    5)          c-1, c+1, 2c( 허용범위 내, 미방문 )
    6)              q 삽입, v[c] 방문처리
"""

import sys
sys.stdin = open( "input.txt", "r")

def bfs(s,e):
    # 초기 q [] 리스트 생성
    q = []
    # 방문정보 리스트 생성( 대략 200_001)
    # 수빈이 90_000, 동생이 100_000일 경우.. 여러 케이스를 생각해보면 200_000도 가능함.
    v = [0] * 200_001

    # 초기 q 삽입
    q.append(s)
    # 방문정보 저장, 초기값 1초를 의미하는 1, 추후 -1
    v[s] = 1

    # q에 데이터가 있을때 까지 무한 반복
    while q:
        # q에서 꺼냄
        c = q.pop(0)
        # q에서 꺼낸 지점과 수빈과 동생의 지점이 같다면
        if c == e:
            return v[e]-1
    
        for n in (c-1, c+1,c*2):
            if 0 <= n <= 200000 and v[n] == 0:
                q.append(n)
                # 방문정보 저장, befor second + 1s
                v[n] = v[c]+1


N,K = map(int, input().split())
ans = bfs(N,K)
print(ans)