BOJ 16953번: A → B

www.acmicpc.net/problem/16953

16953번: A → B

아이디어:

그래프로 풀라고 했으니까 그래프로 풀어야 한다. 이 문제는 DFS로 풀어도 풀리지만(B가만들어지는 경우가 단 하나이기 때문에) 보통은 BFS로 풀어야 더 효율적이다. (DFS는 모든 경우를 구해서 그 중 최솟값을 찾아야 한다.)

2를 곱하거나 -> *2

끝에 1을 추가 -> *10+1

A부터 시작해서 갈 수 있는 경우가 2가지밖에 없으니까 그 방향으로 BFS로 탐색하면서 B가 나오면 도달하기까지 간선의 개수+1를 출력한다.

 

큐에 [변해가는 A의 값, cnt]를 추가하면서 탐색을 진행하고, n[0]이 B보다 큰 경우에는 연결된 다음 그래프를 탐색할 필요가 없으므로 continue를 해준다.

import sys
from collections import deque
a, b = map(int, sys.stdin.readline().split())
q = deque()

q.append([a, 1])
while (q):
    n = q.popleft()
    if (n[0]==b):
        print(n[1])
        sys.exit(0)
    #b보다 큰 경우에는 그래프를 더 그릴 필요가 없음.
    elif (n[0]>b):
        continue
    q.append([n[0]*2, n[1]+1])
    q.append([n[0]*10+1, n[1]+1])
print(-1)