[백준] 16953번 - A → B [Java]

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

 

[백준] 16953번 - A → B [Java]

[백준] 16953번 - A → B [Java]

---

1.  아이디어

 

최단거리 BFS를 활용하면 기본적으로 해결할 수 있고 A에서 B를 찾는 순방향, B에서 A를 찾는 역방향 탐색 모두 가능해서 두 가지 방식으로 해결했다.

---

2. 문제풀이

 

순방향은 문제 조건에 맞춰 조건을 넣고 역방향 탐색은 짝수여부와 1의 자리수가 1인지 여부를 조건으로 설정하면 된다. 방문 체크 배열이 너무 커질 수 있어서 Set 자료구조로 방문체크를 진행했다.

---

3. 코드

 

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 dist = bfs(A, B);

        if (dist == -1) System.out.println(dist);
        else System.out.println(dist + 1);
    }

    private static int bfs(long A, long B) {
        Queue<Long> q = new ArrayDeque<>();
        q.add(A);

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

        int dist = 0;

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

            for (int i = 0; i < len; i++) {
                long node = q.remove();

                if (node == B) return dist;

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

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

            dist++;
        }

        return -1;
    }

}

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

public class Main2 {
    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 dist = bfs(A, B);

        if (dist == -1) System.out.println(dist);
        else System.out.println(dist + 1);
    }

    private static int bfs(long A, long B) {
        Queue<Long> q = new ArrayDeque<>();
        q.add(B);

        Set<Long> visited = new HashSet<>();
        visited.add(B);

        int dist = 0;

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

            for (int i = 0; i < len; i++) {
                long node = q.remove();

                if (node == A) return dist;

                if ((node % 2 == 0) && !visited.contains(node / 2) && (node / 2) >= A) {
                    q.add(node / 2);
                    visited.add(node / 2);
                }

                if ((node % 10 == 1) && !visited.contains((node - 1) / 10) && ((node - 1) / 10) >= A) {
                    q.add((node - 1) / 10);
                    visited.add((node - 1) / 10);
                }
            }

            dist++;
        }

        return -1;
    }

}

---

4. 후기

 

- 순방향 탐색

- 역방향 탐색