[BOJ 16953] A → B

🔗Link

문제
풀이

💡Idea

• bfs 문제이다. 수직선 상에서 갈 수 있는 길이 ‘현재 지점의 2배‘와 ‘현재 지점의 10배 + 1’ 두가지라고 생각하면 된다.
• 현재 지점의 10배 + 1의 경우 int 범위를 초과할 수 있기 때문에 자료형을 넉넉히 long long으로 설정하였다.
• 방문한 여부와 거리를 체크하는 vis 변수의 자료형의 경우, A와 B의 범위를 고려하여 해시 테이블을 사용하였다.

🔑Code

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

int A, B, answer = -1;
queue<long long> Q;
unordered_map<long long,int> vis;

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> A >> B;
    
    vis[A] = 1;
    Q.push(A);

    while(!Q.empty()){
        long long cur = Q.front(); Q.pop();
        for(long long nxt : {cur * 2, cur * 10 + 1}){
            if(nxt > B || vis[nxt]) continue;
            vis[nxt] = vis[cur]+1;
            if(nxt == B) {
                cout << vis[nxt];
                return 0;
            }
            Q.push(nxt);
        }
    }

    cout << answer;

    return 0;
}

🗨️ Side Notes

오늘 하루도 화이팅! 😉