[DFS] BJ16953 A → B

문제 출처: https://www.acmicpc.net/problem/16953

 

Solution

• DFS로 갈 수 있는 길을 탐색하며 A를 B로 변환할 수 있는지 확인한다.

Point

• 좌표를 움직이며 목표 지점에 도달할 수 있는 지를 묻는 경로 탐색 문제이다.
• 주의할 점은 문제의 조건에서 B의 최대 값이 10^9 인데, 이동 시에 끝에 1을 붙이는 연산은 자릿 수를 1 늘리게 되어 int 범위를 넘어가게 된다. 따라서 반드시 long long 을 사용해야 한다.
• 참고로 int는 4btye(32bit)를 사용하며 범위는 –2,147,483,648 to 2,147,483,647이고, long long은 8byte(64bit)를 사용하며 범위는 –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807이다. 즉, int는 자릿수로 따지면 10^9까지만 담을 수 있다.

---

#include <iostream>
#include <algorithm>

using namespace std;

long long A, B;
int result = 987654321;

bool dfs(long long cur, int d) {
    if (cur > B) return false;
    for (int i = 0; i < 2; i++) {
        long long tmp = A;
        if (i == 0) A *= 2;
        else A = A * 10 + 1;
        if (A == B) { result = min(result, d + 1); return true; }
        if(dfs(A, d + 1)) return true;
        A = tmp;
    }
    return false;
}

int main() {
    cin >> A >> B;
    if(dfs(A, 0)) cout << result + 1 << endl;
    else cout << -1 << endl;
}