[백준] 16953 A → B(Silver.2) - BFS

문제

A → B

코드

DFS나 Greedy로 풀 수 있지만 BFS를 공부중이기 때문에 BFS 방식으로 풀었다.
이 문제는 인접 행렬이나 인접 리스트를 구현할 필요가 없기 때문에 큐와 방문 여부 체크만 체크하여 풀었다.

• 풀이 방법

1. 노드의 값과 level을 저장할 큐를 선언하여 초기 값을 저장한다.

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

2. 큐에서 값을 빼고 현재 값 * 2, 현재 값 + "1"을 구한다.

long[] current = queue.poll();
            long cvalue = current[0];
            long clevel = current[1];
            long two = cvalue * 2;
            long one = Long.parseLong(Long.toString(cvalue) + "1");

3. 2에서 구한 값 중 B와 같은 값이 있다면 값의 level을 반환하고 2에서 구한 값이 B보다 작다면 큐에 값과 level을 추가한 후 2번을 반복한다.

while (!queue.isEmpty()) {
            long[] current = queue.poll();
            long cvalue = current[0];
            long clevel = current[1];
            long two = cvalue * 2;
            long one = Long.parseLong(Long.toString(cvalue) + "1");
            if (two == B || one == B) {
                level = clevel + 1;
                break;
            }
            if (two < B) {
                queue.offer(new long[] {two, clevel+1});
            }
            if (one < B) {
                queue.offer(new long[] {one, clevel+1});
            }
        }

전체 코드

• 방문 여부를 체크하기 위해 HashSet을 사용하였는데 이 문제에서는 방문 여부를 체크하지 않아도 괜찮다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _16953 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int result = -1;

        String[] input = br.readLine().split(" ");
        int A = Integer.parseInt(input[0]);
        int B = Integer.parseInt(input[1]);

        System.out.println(BFS(A, B));

    }

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

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

        // int로 선언시 int 범위를 넘어가 런타임 에러 (NumberFormat) 발생하여 long으로 선언.
        long level = -1;

        while (!queue.isEmpty()) {
            long[] current = queue.poll();
            long cvalue = current[0];
            long clevel = current[1];
            long two = cvalue * 2;
            long one = Long.parseLong(Long.toString(cvalue) + "1");
            if (two == B || one == B) {
                level = clevel + 1;
                break;
            }
            if (two < B && !visited.contains(two)) {
                queue.offer(new long[] {two, clevel+1});
                visited.add(two);
            }
            if (one < B && !visited.contains(one)) {
                queue.offer(new long[] {one, clevel+1});
                visited.add(one);
            }
        }
        return level;
    }
}