[BOJ] 1697번 숨바꼭질 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static final int MAX_VAL = 100001;
    static int N, K, result;
    static boolean[] used = new boolean[MAX_VAL];

    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());
        K = Integer.parseInt(st.nextToken());
        result = Integer.MAX_VALUE;

        if (N >= K) result = N - K;
        else bfs();
        System.out.println(result);
    }

    private static void bfs() {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(N, 0));
        used[N] = true;
        while (!q.isEmpty()) {
            Pos now = q.poll();
            int x = now.x;
            int time = now.time;
            if (x == K) {
                result = Math.min(result, time);
                return;
            }
            for (int i = 0; i < 3; i++) {
                int nx = 0;
                if (i == 0) {
                    nx = x-1;
                } else if (i == 1) {
                    nx = x+1;
                } else {
                    nx = 2*x;
                }
                if (isOutOfRange(nx)) continue;
                if (used[nx]) continue;
                used[nx] = true;
                q.add(new Pos(nx, time+1));
            }
        }
    }

    private static boolean isOutOfRange(int nx) {
        return nx < 0 || nx >= MAX_VAL;
    }

    static class Pos {
        int x;
        int time;

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

📄 해설

- 도저히 풀지를 못해서 솔루션을 확인한 문제. 다음주 주말을 이용해서 다시 풀어봐야함

• 해결해놓고 한참동안 수정하는걸 깜빡한 작성자의 뛰어난 기억력
• 아래의 세가지 경우 탐색을 모두 해야하므로 BFS 를 사용하여 탐색을 하는 문제
  1. x-1 에 대한 탐색
  2. x+1 에 대한 탐색
  3. x*2 에 대한 탐색
• 방문하지 않았고, 범위를 벗어나지 않으면 해당 위치를 큐에 넣고 계속해서 탐색을 수행
• BFS 를 호출하는 시점에 대한 처리를 놓치기가 쉬운데, N>=K 인 경우. 그러니까 문제의 수빈이가 동생과 같은 위치에 있거나, 동생보다 앞서 있는 경우의 처리를 말함
  • 이 경우, 수빈이는 뒤로 이동할 수 밖에 없음 -> 탐색은 x-1 의 경우만 가능하므로, 결과는 자연스레 N-K 가 됨