[백준 16953] A → B(Java)

[백준 16953] A → B(Java)

16953번: A → B

해결 방법

DFS또는 BFS 를 사용해서 해결하면 됩니다.👍

연산의 종류에 따라서 자료 구조에 데이터를 삽입하고 꺼내는 것을 목표값을 찾을 때 까지 반복 합니다.

2023.03.19 - [0 + 알고리즘(Algorithm)] - [알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java)

[알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java)

2023.03.16 - [0 + 알고리즘(Algorithm)] - [알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java)

[알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java)

 

자세한 풀이는 코드와 주석을 보시면 쉽게 이해하실 수 있을 것 입니다.

 

참고로 저는 재귀 함수를 구현하는것에 많이 약합니다. ㅠㅠ
저 처럼 재귀 함수를 사용하것에 약하신 분들은 직접 Stack 자료구조를 사용해 보시는 걸 추천 드립니다.

풀이

반응형

DFS(재귀)

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

        int number = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

        // dfs 수행
        dfs(number, target, 0);

        if(myDepth == 0) myDepth = -1;

        System.out.print(myDepth);
        br.close();
    }

    private static void dfs(long number, int target, int depth) {
        if(number == target) {
            // 그래프의 깊이가 연산 횟수에 해당한다.
            myDepth = depth + 1;
            return;
        }
        // 곱하기 연산
        long case1 = number * 2L;
        // 일의 자리 뒤에 1을 추가하는 연산
        long case2 = number * 10L + 1L;
        if(case1 <= target) {
            // case1 그래프의 깊이를 1 증가
            dfs(case1, target, depth + 1);
        }
        if(case2 <= target) {
            // case2 그래프의 깊이를 1 증가
            dfs(case2, target, depth + 1);
        }
    }
}

 

DFS(스택)

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 number = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

        // dfs 수행
        System.out.println(dfsWithStack(number, target));
        br.close();
    }

    private static int dfsWithStack(long number, int target) {
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(number, 0));

        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            // 타겟 값을 찾으면
            if(pop.getNumber() == target) {
                // 깊이 + 1 반환
                return pop.getDepth() + 1;
            }

            // 곱하기 연산
            long case1 = pop.getNumber() * 2L;
            // 일의 자리에 1을 추가하는 연산
            long case2 = pop.getNumber() * 10L + 1L;
            // 깊이 1 증가
            int depth = pop.getDepth() + 1;

            if(case1 <= target) {
                // 스택에 데이터 삽입
                stack.push(new Node(case1, depth));
            }
            if(case2 <= target) {
                // 스택에 데이터 삽입
                stack.push(new Node(case2, depth));
            }
        }

        return -1;
    }

    static class Node {
        private long number;
        private int depth;

        public Node(long number, int depth) {
            this.number = number;
            this.depth = depth;
        }

        public long getNumber() {
            return number;
        }

        public int getDepth() {
            return depth;
        }
    }
}

 

BFS

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 number = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

        long bfs = bfs(number, target);
        System.out.print(bfs);
        br.close();
    }
    private static long bfs(int number, int target) {
        Queue<Node> q = new ArrayDeque<>();
        int count = 0;
        q.offer(new Node(number, count));

        while (!q.isEmpty()) {
            Node poll = q.poll();

            // 타겟 값을 찾으면
            if(poll.getNumber() == target) {
                return poll.getCount() + 1;
            }

            count = poll.getCount() + 1;
            long case1 = poll.getNumber() * 2L;
            long case2 = poll.getNumber() * 10L + 1L;

            // 타겟값보다 작거나 숫자만 큐에 삽입
            if(case1 <= target) {
                q.add(new Node(case1, count));
            }
            if(case2 <= target) {
                q.add(new Node(case2, count));
            }
        }

        return -1;
    }

    static class Node {
        private long number;
        private int count;

        public Node(long number, int count) {
            this.number = number;
            this.count = count;
        }

        public long getNumber() {
            return number;
        }

        public int getCount() {
            return count;
        }
    }
}