[BOJ/JAVA] 13549번: 숨바꼭질 3

태그: Java

13549번: 숨바꼭질 3

13549번: 숨바꼭질 3

키워드

수빈이가 이동하는 방법은 총 3가지 이다.

1. X-1로 이동하는 경우
2. X+1로 이동하는 경우
3. 2 * X 로 이동하는 경우 (이 때는 시간이 소모되지 않는다.)

가장 빠른 시간을 구해야 하므로, 너비우선탐색을 이용하여 3가지 경우 모두 탐색한다.

---

최적화

항상 3가지 경우를 모두 탐색해야 할까?

그건 아니다.

• 2 * X 이동을 하는 경우는 수빈이의 현재 위치(X)가 동생의 위치(K) 보다 작을 때 이동을 하면 된다.
• X + 1 이동을 하는 경우는 마찬가지로 수빈이의 현재 위치(X)가 동생의 위치(K) 보다 작을 때 이동을 하면 된다.
• X - 1 이동은 점의 최솟값이 0 이상이므로 0일때는 X - 1이동을 하지 않는다.

---

구현

dist[] 배열을 선언했다.

dist 배열은 수빈이가 현재 [i]위치에 있을 때 최단시간을 갱신하는 배열이다.

예를 들어 dist[100] 이면 수빈이가 100위치에 있을 때 최단경로를 반환하도록 한다.

그러기 위해서 이동했을 때의 시간이 저장되어있을 때의 시간보다 짧다면 갱신하는 방식을 취한다.

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class java_13549 {
    // 수빈이의 위치
    static int N;
    // 동생의 위치
    static int K;

    static int dist[] = new int[100001];

    static class Pair {
        int here;
        int second;

        public Pair(int here, int second) {
            this.here = here;
            this.second = second;
        }
    }

    static void findRoute(int here, int second) {

        Deque<Pair> deque = new ArrayDeque<>();

        deque.add(new Pair(here, 0));

        while (!deque.isEmpty()) {
            Pair now = deque.poll();

            // 만난다면...
            if (now.here == K) {
                if (now.second < dist[now.here]) {
                    dist[now.here] = now.second;
                }
            }

            else {
                try {
                    if (now.here < K) {
                        if (now.second < dist[now.here * 2]) {
                            dist[now.here * 2] = now.second;
                            deque.add(new Pair(now.here * 2, now.second));
                        }
                    }
                } catch (IndexOutOfBoundsException exception) {
                }

                try {
                    if (now.here < K) {
                        if (now.second + 1 < dist[now.here + 1]) {
                            dist[now.here + 1] = now.second + 1;
                            deque.add(new Pair(now.here + 1, now.second + 1));
                        }
                    }
                } catch (IndexOutOfBoundsException exception) {
                }

                try {
                    if (now.second + 1 < dist[now.here - 1]) {
                        dist[now.here - 1] = now.second + 1;
                        deque.add(new Pair(now.here - 1, now.second + 1));
                    }
                } catch (IndexOutOfBoundsException exception) {
                }

            }

        }

        return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 데이터 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        Arrays.fill(dist, Integer.MAX_VALUE);

        // 수빈이가 가는 방법 X+1, X-1, 2*X
        findRoute(N, 0);

        System.out.println(dist[K]);

        bw.close();
        br.close();
    }
}

---