[백준16953&파이썬] BFS를 이용해 1차원 탐색하기

# 문제

백준166953 A->B 파이썬 풀이

16953번: A → B

# 코드

'''
  - BFS를 이용한 전형적인 풀이 같다.
'''
import sys
from collections import deque
from collections import defaultdict

A, B = map(int, sys.stdin.readline().split())
dq = deque()
visit = defaultdict(bool)
dq.append((A, 1))
visit[A] = True  # 초기 방문

while len(dq) != 0:
  cur = dq.popleft()  # ( node, cnt )

  next1 = (cur[0] * 2, cur[1] + 1)
  next2 = ((cur[0] * 10) + 1, cur[1] + 1)

  if next1[0] == B or next2[0] == B:
    print(next1[1])
    exit()

  if visit[next1[0]] == False and next1[0] <= B:
    dq.append(next1)
    visit[next1[0]] = True

  if visit[next2[0]] == False and next2[0] <= B:
    dq.append(next2)
    visit[next2[0]] = True

print(-1)

# 풀이

• BFS를 이용한 전형적인 최단거리 탐색이다.
• next로 append할 조건에 유의한다. *2와 *10 + 1 두가지 경우이다.
• 종료조건에 대한 고민이 필요하며, 종료조건은 B의 값을 넘었을때이다. 다시 뒤로 돌아올 일은 없기 때문에 해당 값을 지나치면 풀 수 없는 문제다.