자바(Java) 알고리즘 문제풀이 A->B [백준 / DFS]

출처 - 구글 이미지

 

 

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

16953번: A → B

 

 

풀이 코드

DFS 기본 문제와 아주 유사한 완전탐색 문제이다. 

if-else 구문을 사용해서 if 절에는 출력 값을 결정해주는 탈출 구문을 작성하고 else 절에서 DFS() 를 두 가지 방식으로 호출하면 된다.

유의할 점은, 1을 수의 가장 오른쪽에 추가하는 부분인데 반례에 int 범위를 넘어가는 수가 나오므로 A 는 int 가 아닌 long 타입으로 받자.

그리고 StackOverFlow 예외를 방지하기 위해 재귀 호출 시 A 가 B 보다 큰 경우는 탐색할 필요가 없으므로 빠져나오도록 구현했다.

마지막으로 count 가 그대로 0 이라면 B 가 되는 아무런 방법이 없다는 뜻이므로 -1 를 출력하도록 하면 끝.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static long a;
    static int b;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Long.parseLong(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        DFS(a, 1);

        if (count == 0) {
            System.out.println(-1);
        } else {
            System.out.println(count);
        }
    }

    private static void DFS(long a, int depth) {
        // if 구문에서 탈출조건 부여
        if (a == b) {
            count = depth;
            return;

        // 2가지의 경우로 depth 를 증가시키면서 완전탐색하도록 로직 작성
        } else {
            if (a > b) {
                return;
            } else {
                DFS(a * 2, depth + 1);
                DFS(Long.parseLong(String.valueOf(a) + 1), depth + 1);
            }
        }
    }
}

// 2를 곱하너가 1을 수의 가장 오른쪽에 추가하는 방법 2가지
// A 를 B 로 바꾸는데 필요한 연산의 최솟값은 ?