백준 - 숨바꼭질 (JAVA)

문제링크

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

---

풀이 및 알고리즘

BFS 레벨탐색으로 해결

중복방문이 불가능하므로, check배열을 만들어 중복을 검사하고, queue를 통해 bfs를 돌리면 끝

---

코드

public class Baekjoon_1697 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Queue<Integer> queue = new LinkedList<>();
        int[] ch = new int[100001];
        queue.offer(n);
        ch[n] = 1;
        int L = 0;

        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                int temp = queue.poll();
                if (temp == k) {
                    System.out.println(L);
                    return;
                }
                for (int x : new int[]{temp - 1, temp + 1, temp * 2}) {
                    if (x >= 0 && x <= 100000 && ch[x] == 0) {
                        ch[x] = 1;
                        queue.offer(x);
                    }
                }
            }
            L++;
        }
    }