"""
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)
'Algorithm' 카테고리의 다른 글
[BaekJoon] 백준 알고리즘 1759번 / 암호 만들기 / 백트래킹(DFS) / Python (1) | 2023.03.07 |
---|---|
[BaekJoon] 백준 알고리즘 14889번 / 스타트와 링크 / 백트래킹(DFS) / Python (0) | 2023.03.07 |
[BaekJoon] 백준 알고리즘 1260번 / DFS와 BFS / Python (0) | 2023.03.03 |
[BaekJoon] 백준 알고리즘 14503번 / 로봇 청소기 / 시뮬레이션 / Python (0) | 2023.03.02 |
[BaekJoon] 백준 알고리즘 14888번 / 연산자 끼워넣기 / 백트래킹 / Python (0) | 2023.03.01 |