[伯俊]1697号鬼ごっこ-Java,Java

難易度

銀色.

質問する

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

に答える

最速時間を探す必要がある問題なのでBFSでアクセスしました.
この問題でうろうろしている点は,費やした時間をcountでコードに書き,結果が大きすぎることである.
時間の処理方法を考慮し,1次元配列格納方式で問題を解決した.
BFSの問題については、通常、アレイに値を格納し、問題を解決します(ex.tom).
この問題もこのように合わせて解けばいい.

コード#コード#

package 그래프탐색;


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 BOJ1697 {
    static int n, k;
    static int[] arr;
    static Queue<Integer> q = new LinkedList<>();

    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());


        if (n >= k) {
            System.out.println(n - k);
        } else {
            System.out.println(bfs());
        }

    }

    static int bfs() {

        // 시간을 저장하는 배열선언
        arr = new int[100001];
        q.add(n);
        arr[n] = 1;
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int i = 0; i < 3; i++) {
                int nx;
                if (i == 0)
                    nx = x - 1;
                else if (i == 1)
                    nx = x + 1;
                else
                    nx = x * 2;

                if (nx == k)
                    return arr[x];

                if (nx >= 0 && nx < 100001 && arr[nx] == 0) {
                    arr[nx] = arr[x] + 1;
                    q.add(nx);
                }
            }
        }
        return 0;
    }

}