[백준 / 골드5] 13549 숨바꼭질 3 (Java)

문제 보기

사용한 것

• 동생을 찾는 최소 시간을 구하기 위한 BFS

풀이 방법

• 순간이동(2 X x), 한칸 뒤로(x - 1), 한칸 앞으로(x + 1)를 q에 넣으면서 현재 x가 K와 같으면 answer에 time을 넣어주고 break
  • 2배로 이동한 값(0초 소요)이 +1로 이동한 값(1초 소요)보다 항상 먼저 계산되어 q에 들어가므로, 처음으로 K가 나온 시간이 항상 최소 시간이다.
• answer 출력

코드

public class Main {

    static final int MAX = 100_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int K = Integer.parseInt(line[1]);

        boolean[] visited = new boolean[MAX + 1];
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(N, 0));

        int answer = -1;

        while (!q.isEmpty()) {
            Point p = q.poll();
            int x = p.getX();
            int time = p.getTime();

            visited[x] = true;

            if (x == K) {
                answer = time;
                break;
            }

            if (x != 0 && 2 * x <= MAX && !visited[2 * x]) {
                q.offer(new Point(2 * x, time));
            }
            if (x - 1 >= 0 && !visited[x - 1]) {
                q.offer(new Point(x - 1, time + 1));
            }
            if (x + 1 <= MAX && !visited[x + 1]) {
                q.offer(new Point(x + 1, time + 1));
            }
        }

        System.out.println(answer);
    }
}

class Point {

    private int x;
    private int time;

    public Point(int x, int time) {
        this.x = x;
        this.time = time;
    }

    public int getX() {
        return x;
    }

    public int getTime() {
        return time;
    }
}