A->B - 16953

문제

https://www.acmicpc.net/problem/16953

느낀점

하나의 루트로 갈 때 최단거리와 같은 비용을 계산할 때, bfs를 많이 사용하는데, 가짓수를 셀 때도 이러한 방식으로 접근하면 유용하다는 것을 배웠다.

풀이

#include <iostream>
#include <queue>

#define pii std::pair<long, long>

int main()
{
    long A, B;
    std::cin >> A >> B;

    std::queue<pii> queue;
    queue.push(std::make_pair(A, 0));

    while (!queue.empty())
    {
        pii temp = queue.front();
        queue.pop();
        if (temp.first == B)
        {
            std::cout << temp.second + 1;
            return 0;
        }

        if (temp.first * 2 <= B)
        {
            queue.push(std::make_pair(temp.first * 2, temp.second + 1));
        }

        if (temp.first * 10 + 1 <= B)
        {
            queue.push(std::make_pair(temp.first * 10 + 1, temp.second + 1));
        }
        }

    std::cout << -1;
    return 0;
}