(매일 BOJ) C++ 16953번 A -> B

이번 문제는 16953번 A ->  B 이다

문제 요약

• 허용 연산
  1. x → 2x
  2. x → 10x + 1
• 목표: A에서 시작해 B에 도달하는 최소 단계 수 + 1을 출력 (도달 불가 시 -1)

접근법

• BFS(너비 우선 탐색)
  시작값 A를 루트로 상태를 확장합니다. 간선 가중치가 모두 1이므로, 처음 B를 만나는 순간의 레벨이 곧 정답이다
  • 상태: 현재 값 x
  • 간선: x → 2x, x → 10x + 1
  • next > B는 확장할 필요가 없으므로 가지치기
  • 방문/거리 관리는 map(또는 unordered_map)으로 처리
• (참고) 역방향 그리디(B → A) 도 매우 간단하다 B의 끝이 1이면 /10, 아니고 짝수면 /2, 그 외는 실패

작성코드

#include <bits/stdc++.h>
using namespace std;

int BFS(long long a, long long b);

int main (void){
    long long A,B;
    cin >> A >> B;
    int answer = BFS(A,B);
    cout << answer;

    return 0;

}

int BFS (long long a, long long b){
    queue<long long> q;
    map<long long, long long> distance;
    q.push(a);
    distance[a] = 1;

    while(!q.empty()){
        long long current = q.front();
        q.pop();
        if(b == current) return distance[current];

        for(long long next : {current*2,current*10+1}){
            
            
            if(next <= b && !distance.count(next)){
                distance[next] = distance[current] + 1;
                q.push(next);
            }
            
            if(b == next) return distance[next];
        }
    }
    return -1;
}