16953 - A → B

이 문제는 시작점 A에서 끝점 B로 가는 최소 연산 수를 구해야 하는 문제이다. 이때 2를 곱하는 연산과 1을 수의 가장 오른쪽에 추가하는 두 가지 연산이 가능하다.

먼저 이 문제는 BFS를 통해 풀 수 있다. 숫자를 정점으로 보고, 연산을 간선으로 봐 BFS를 적용하면 그 숫자에 처음 도달한 경로를 최소 연산 수로 확정할 수 있다.

그런데 이 문제의 특징은 어떠한 수로 가는 경로(연산의 나열)은 반드시 하나밖에 없다는 것이다. A에서 한 번 이상의 연산을 통해 생성한 어떠한 수 N을 가정하자. N은 2x이거나 10y+1 로 나타낼 수 있다. (x, y는 직전 단계의 자연수이다.) 그런데 만약 N = 2x라면 10y+1로 나타낼 수 없고, N = 10y+1이라면 2x로 나타낼 수 없다. 즉 연산 한 번을 이용해 어떠한 수 N으로 도달할 수 있는 수는 오직 하나이다. 이 사실은 A에서 한 번 이상 연산을 적용한 모든 수에 대해 성립하므로 A에서 연산의 반복을 통해 N을 만들 수 있는 경로는 오직 하나임을 알 수 있다.

따라서 그리디 알고리즘으로 B에서부터 A까지 역추적하는 알고리즘을 짜면 더 효율적으로 문제를 해결할 수 있다.

🔗 문제 링크

코드

BFS로 푼 경우

먼저 정점을 표현하는 Node 클래스를 만든다. 정점의 값(숫자)와 연산 횟수를 저장하도록 한다.

class Node {
    public long val;
    public int cnt;

    public Node(long val, int cnt) {
        this.cnt = cnt;
        this.val = val;
    }
}

다음으로 A, B를 입력받는다. 그리고 BFS를 위해 큐를 생성한 뒤 탐색을 시작하는 지점인 a를 넣는다. 문제에서 필요한 연산의 최솟값에 1을 더한 값을 출력하라고 하였으므로, cnt에는 0이 아닌 1을 넣는다.

public static void main(String[] args) throws IOException {
    StringTokenizer s = new StringTokenizer(br.readLine());
    long a = Long.parseLong(s.nextToken());
    long b = Long.parseLong(s.nextToken());

    Deque<Node> queue = new ArrayDeque<>();
    queue.addLast(new Node(a, 1));

이제 결과를 담아둘 result 변수를 선언하고, BFS 탐색을 시작한다. 제일 앞에서 노드를 꺼낸 뒤 노드 값을 먼저 확인한다. 만약 노드의 값이 목표인 B와 같다면 결과를 result 변수에 저장하고 break를 통해 빠져나온다. 같지 않다면 인접 노드를 탐색한다. 인접 노드는 node.val * 2, node.val * 10 + 1일 것이다. 이 인접 노드들에 대해 B보다 값이 크지 않다면 다음 탐색 후보로 큐에 넣는다. 중복 검사를 하지 않는 이유는 연산이 단조 증가 함수이고, 앞서 언급했듯 어떤 노드로 도달하는 경로가 한 가지밖에 없어서 항상 중복되지 않음을 보장하기 때문이다. 마지막으로 결과를 출력하고 프로그램을 종료한다. 만약 b와 같은 값을 가지는 노드를 찾았다면 그 노드의 cnt 값을 출력할 것이고, 찾지 못했다면 초기화 값인 -1이 출력될 것이다.

    int result = -1;
    while (!queue.isEmpty()) {
        Node node = queue.pop();
        if (node.val == b) {
            result = node.cnt;
            break;
        }
        List<Long> adjs = List.of(node.val * 2, node.val * 10 + 1);
        for (long adj : adjs) {                
            if (adj > b) continue;
            queue.addLast(new Node(adj, node.cnt + 1));
        }
    }

    bw.write(result + "\n");
    bw.flush();

그리디로 푼 경우

입력 부분은 위와 동일하므로 생략하고 바뀐 부분만 살펴보자.

앞서 말했듯이 두 연산이 배타적이라고 하였으므로, 역행이 가능한 연산이 어떤 것인지 확인하고 가능한 쪽으로 돌아가는 방식으로 구현하면 된다.

먼저 cur이 a와 같은지 확인하고 a와 같다면 루프를 빠져나오게 한다. 만약 2로 나누어떨어진다면 x = cur / 2이므로 cur /= 2로 업데이트한다. 반대로 10으로 나누었을 때 나머지가 1이라면 y = (cur - 1) / 10 이므로 cur /= 10 으로 업데이트한다. (정수 연산이므로 1은 빼지 않아도 된다) 적용한 연산의 수를 세기 위해 루프가 한 번 돌 때마다 cnt를 1 증가시킨다.

만약 두 연산을 모두 적용할 수 없으면, B는 A로부터 생성할 수 있는 수가 아니므로 -1을 출력하고 바로 프로그램을 끝낸다. 반대로 정상적으로 루프를 빠져나왔다면 cnt+1을 출력하고 프로그램을 종료한다.

    int cnt = 0;
    long cur = b;

    while (true) {
        if (cur == a) 
            break;

        if (cur % 2 == 0 && cur / 2 >= a) {
            cur /= 2;
        }
        else if (cur % 10 == 1 && cur / 10 >= a) {
            cur /= 10;
        }
        else {
            bw.write(-1 + "\n");
            bw.flush();
            return;
        }
        cnt++;
    }
    
    bw.write((cnt+1) + "\n");
    bw.flush();

전체 코드

BFS로 푼 경우

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

class Node {
    public long val;
    public int cnt;

    public Node(long val, int cnt) {
        this.cnt = cnt;
        this.val = val;
    }
}

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        StringTokenizer s = new StringTokenizer(br.readLine());
        long a = Long.parseLong(s.nextToken());
        long b = Long.parseLong(s.nextToken());

        Deque<Node> queue = new ArrayDeque<>();
        queue.addLast(new Node(a, 1));

        int result = -1;
        while (!queue.isEmpty()) {
            Node node = queue.pop();
            if (node.val == b) {
                result = node.cnt;
                break;
            }
            List<Long> adjs = List.of(node.val * 2, node.val * 10 + 1);
            for (long adj : adjs) {                
                if (adj > b) continue;
                queue.addLast(new Node(adj, node.cnt + 1));
            }
        }
    
        bw.write(result + "\n");
        bw.flush();
    }
}

그리디로 푼 경우

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

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        StringTokenizer s = new StringTokenizer(br.readLine());
        long a = Long.parseLong(s.nextToken());
        long b = Long.parseLong(s.nextToken());

        int cnt = 0;
        long cur = b;

        while (true) {
            if (cur == a) 
                break;

            if (cur % 2 == 0 && cur / 2 >= a) {
                cur /= 2;
            }
            else if (cur % 10 == 1 && cur / 10 >= a) {
                cur /= 10;
            }
            else {
                bw.write(-1 + "\n");
                bw.flush();
                return;
            }
            cnt++;
        }
        
        bw.write((cnt+1) + "\n");
        bw.flush();
    }
}

시간복잡도

BFS로 푼 경우, 큐에 들어가는 값은 모두 서로 다른 값임을 알 수 있다. 왜냐하면 앞서 언급했듯 각 수를 만들 수 있는 경로는 단 하나이기 때문이다. 또한 값이 최대 B인 노드까지만 탐색하므로, 방문 가능한 서로 다른 값의 개수는 최대 $B - A + 1 \le B$ 개이고, 각 방문마다 연산 2개를 체크하므로 BFS의 시간복잡도는 $O(2B) = O(B)$ 이다.

그리디의 경우 A가 될 때까지 수를 2 또는 10으로 나누게 되며 따라서 반복문은 $O(\log B)$ 에 비례하는 횟수만큼 돌게 된다.

결과적으로 그리디를 이용한 풀이법이 BFS를 이용한 풀이법보다 시간복잡도 면에서 빠른 것을 확인할 수 있다.