[백준] BOJ_1697 숨바꼭질 JAVA

BOJ_1697 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

---

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

예제 입&출력

---

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int n, k;
    private static boolean[] map;
    private static final int MAX = 100_001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();

        map = new boolean[MAX];

        Queue<Info> q = new LinkedList<>();
        q.add(new Info(n, 0));
        map[n] = true;

        while (!q.isEmpty()) {
            int cur = q.peek().x;
            int cnt = q.peek().cnt;

            q.poll();

            if (cur == k) {
                System.out.println(cnt);
                break;
            }

            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) {
                    next = cur - 1;
                } else if (i == 1) {
                    next = cur + 1;
                } else {
                    next = 2 * cur;
                }

                if (!inScope(next)) continue;

                if (!map[next]) {
                    q.add(new Info(next, cnt + 1));
                    map[next] = true;
                }
            }
        }
    }

    private static boolean inScope(int num) {
        return num >= 0 && num < MAX;
    }

    private static class Info {
        int x;
        int cnt;

        public Info(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }
    }
}

---

Comment

• bfs 좌표 문제와 다를 것 없다. 3가지 경우가 있다.
  • 현재 지점 - 1
  • 현재 지점 + 1
  • 현재 지점 * 2
• 최소 Count를 위해 Info에 좌표 정보(x)와 카운팅(cnt)를 넣었다.

---