[알고리즘-BFS] 숨바꼭질

문제 제목 : 숨바꼭질

난이도 : 하

문제 유형 : BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

1697번: 숨바꼭질

 

import java.util.*;

public class Main {
    public static int n, k;
    public static int MAX = 100001;
    public static boolean[] visited = new boolean[MAX];
    public static int[] time = new int[MAX];

    public static Integer bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        visited[n] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if (now == k) return time[now];

            int next = now - 1;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }

            next = now + 1;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }

            next = now * 2;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        System.out.println(bfs());
    }
}