[BaekJoon] 16953번 - A → B [Java][C++]

문제 링크

---

1. 문제 풀이

정수 $A$ 를 $B$ 로 바꾸는 문제로 최단 거리 BFS를 활용해서 $A$ 또는 $B$ 에 각 연산을 적용해보며 수가 나오는지 판단하는 방식으로 풀 수도 있고, 그리디 알고리즘을 활용하여 $B$ 를 $A$ 가 되는지 판단하는 방식으로도 해결할 수 있다.

$B$ 가 현재 짝수일 경우는 이전 수가 첫 번째 연산을 통해 $B$ 가 된 경우만 가능하고, $B$ 가 현재 홀수일 경우 이전 수가 두 번째 연산을 통해 $B$ 가 됐거나 아니면 그런 이전 수가 없는 경우만 존재한다.

---

2. 코드

1. BFS [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int result = bfs(A, B);
        System.out.println(result);
    }

    static int bfs(int A, int B) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(A);

        Set<Integer> visited = new HashSet<>();
        visited.add(A);

        int dist = 1;

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int node = q.poll();
                if (node == B) return dist;

                if (node * 2L <= B && !visited.contains(node * 2)) {
                    q.offer(node * 2);
                    visited.add(node * 2);
                }

                if (node * 10L + 1 <= B && !visited.contains(node * 10 + 1)) {
                    q.offer(node * 10 + 1);
                    visited.add(node * 10 + 1);
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 그리디 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        boolean flag = false;
        int cnt = 1;
        while (true) {
            if (A == B) {
                flag = true;
                break;
            } else if (A > B) {
                break;
            }

            if (B % 2 == 0) {
                B /= 2;
            } else if (B % 10 == 1) {
                B /= 10;
            } else {
                break;
            }

            cnt++;
        }

        if (flag) {
            System.out.println(cnt);
        } else {
            System.out.println(-1);
        }
    }
}

3. BFS [C++]

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

int bfs(int a, int b) {
    queue<int> q;
    q.push(a);

    set<int> visited;
    visited.insert(a);

    int dist = 1;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            int node = q.front();
            q.pop();

            if (node == b) return dist;

            if (node * 2LL <= b && !visited.count(node * 2)) {
                q.push(node * 2);
                visited.insert(node * 2);
            }

            if (node * 10LL + 1 <= b && !visited.count(node * 10 + 1)) {
                q.push(node * 10 + 1);
                visited.insert(node * 10 + 1);
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    cin >> a >> b;

    int res = bfs(a, b);
    cout << res;
}

4. 그리디 [C++]

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    cin >> a >> b;

    bool flag = false;
    int cnt = 1;
    while (true) {
        if (a == b) {
            flag = true;
            break;
        } else if (a > b) {
            break;
        }

        if (b % 2 == 0) {
            b /= 2;
        } else if (b % 10 == 1) {
            b /= 10;
        } else {
            break;
        }

        cnt++;
    }

    if (flag) {
        cout << cnt;
    } else {
        cout << -1;
    }
}

---