Algorithm & Data Structures/BOJ

12851. 숨바꼭질2 (Java)

Geisha 2023. 11. 28. 14:43

오랜만에 풀어서 그런지 자잘한 오류가 너무 많았던 문제였다.

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

public class Main {

    static int N, M, answer = 0,time=0;
    static boolean[] isVisited = new boolean[200005];
    public static void BFS() {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(N);
        boolean flag = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for(int i = 0 ; i < size ; i++) {
                int recent = q.poll();
                isVisited[recent] = true;
                if(recent == M){
                    flag=true;
                    answer++;
                }
                if (recent-1>=0 && !isVisited[recent - 1])
                    q.offer(recent - 1);
                if (recent+1<=100000 && !isVisited[recent + 1])
                    q.offer(recent + 1);
                if (recent <= 100000 && !isVisited[recent * 2] )
                    q.offer(recent * 2);
            }
            if(flag)
                break;
            time++;
        }
        System.out.println(time);
        System.out.println(answer);
    }

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        BFS();

    }
}