백준 16953번 "A → B"

백준 16953번 문제 "A →B" 이다.

 

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

 

문제

---

 

예제 입출력

---

 

 

입력	출력
2 162	5
4 42	-1
100 40021	5

 

문제 접근

---

간단한 BFS 문제이다.

 

문제에서 주어진 연산은 2를 곱하거나, 오른쪽에 1을 붙이는 것인데 모두 수를 크게 증가시키는 연산이다. 어떤 수가 들어오더라도 조금만 연산을 반복하면 10^9 을 넘어가므로, 그냥 BFS 를 진행하면서 10^9을 넘어가면 탐색을 진행하지 않게 구현하면 문제가 풀린다.

탐색을 진행하다가 B가 나왔다면 연산 횟수를 출력하면 되고, BFS를 끝까지 돌렸는데도 B가 나오지 않았다면 -1을 출력하면 되는 문제이다.

 

문제 풀이

---

아래는 풀이 코드이다.

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

class Main {

    static Scanner sc = new Scanner(System.in);
    static long A,B;
    static HashSet<Long> pass = new HashSet<Long>();
    
    public static void main(String[] args) {
        A = sc.nextLong();
        B = sc.nextLong();

        long answer = BFS();
        System.out.println(answer);
    }

    static long BFS() {
        Queue<long[]> queue = new LinkedList<>();
        queue.offer(new long[] {A, 1});
        pass.add(A);

        while(!queue.isEmpty()) {
            long[] now = queue.poll();
            long now_num = now[0];
            long now_cnt = now[1];
            
            long next1 = now_num * 2;
            long next2 = Long.parseLong(String.valueOf(now_num) + "1");

            if(next1 == B) {return now_cnt+1;}
            else if(next2 == B) {return now_cnt+1;}

            if(!pass.contains(next1) && next1 < B) {
                pass.add(next1);
                queue.offer(new long[] {next1, now_cnt+1});
            }

            if(!pass.contains(next2) && next2 < B) {
                pass.add(next2);
                queue.offer(new long[] {next2, now_cnt+1});
            }
        }

        return -1;
    }
}

 

자세한 설명은 코드의 각 부분을 살펴보며 진행하도록 하자.

 

- BFS 메소드

    static long BFS() {
        Queue<long[]> queue = new LinkedList<>();
        queue.offer(new long[] {A, 1});
        pass.add(A);

        while(!queue.isEmpty()) {
            long[] now = queue.poll();
            long now_num = now[0];
            long now_cnt = now[1];
            
            long next1 = now_num * 2;
            long next2 = Long.parseLong(String.valueOf(now_num) + "1");

            if(next1 == B) {return now_cnt+1;}
            else if(next2 == B) {return now_cnt+1;}

            if(!pass.contains(next1) && next1 < B) {
                pass.add(next1);
                queue.offer(new long[] {next1, now_cnt+1});
            }

            if(!pass.contains(next2) && next2 < B) {
                pass.add(next2);
                queue.offer(new long[] {next2, now_cnt+1});
            }
        }

        return -1;
    }

 

사실상 문제풀이의 정수가 담겨있는 부분이다.

pass는 지금까지 지나친 숫자들을 저장하기 위해 생성한 HashSet<Integer> 이다. boolean 배열 형태로 방문처리를 하지 않은 이유는, 값이 10^9 까지 나올 수 있으므로 boolean[10^9] 을 선언하는 순간 용량이 너무 커질 것을 우려했기 때문이다.

 

* 지금 계산해보니 Java 에서 boolean은 1byte 이므로 10^9 크기 boolean 배열의 용량은 1000MB 이다. 용량이 초과된다. 앞서 말했듯이 이 문제에서 거쳐가는 숫자는 사실 그리 많지 않다. 숫자가 금방금방 커져서 B를 넘어버리기 때문이다. 따라서 HashSet을 사용하면 용량을 오히려 줄일 수 있다.

 

처음에 큐에 A를 넣어놓고 탐색을 시작하여 다음 값으로 탐색을 이어간다. 이때 B를 발견했다면 카운팅한 값을 넘겨준다.

while 이 끝났는데도 값이 return 되지 않았다면 B를 만들 수 없다는 뜻이므로 -1을 return 하도록 하였다.

 

- main

class Main {

    static Scanner sc = new Scanner(System.in);
    static long A,B;
    static HashSet<Long> pass = new HashSet<Long>();
    
    public static void main(String[] args) {
        A = sc.nextLong();
        B = sc.nextLong();

        long answer = BFS();
        System.out.println(answer);
    }

 

그저 BFS를 실행하기만 하면 문제가 풀린다.