백준 13549번 숨바꼭질 3 (JAVA)

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

13549번: 숨바꼭질 3

 

저는 Best First Search를 통해서 해당 문제를 해결하였습니다. 

저는 우선순위 큐를 통해서 가장 시간이 작은 것을 먼저 나오게 하였습니다.

또한, 2 * 100,000 까지만 가도록 하였습니다. 동생이 0부터 100,000사이에만 존재하기 때문에 2 * 100,000 이상 이동하는 것은 의미 없다고 생각하였습니다.

 

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_13549 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Function<String, Integer> stoi = Integer::parseInt;
        int start = stoi.apply(st.nextToken());
        int end = stoi.apply(st.nextToken());
        int result = bfs(start, end);
        System.out.println(result);
    }

    private static final int LIMIT = 2 * 100_000;
    private static final int NOT_FOUND = -1;

    private static int bfs(int start, int end) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            return o1[1] - o2[1];
        });
        Map<Integer, Integer> visited = new HashMap<>();
        pq.offer(new int[]{start, 0});
        visited.put(start, 0);
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            if (now[0] == end) {
                return now[1];
            }
            for (int i = -1; i <= 1; i++) {
                int time = now[1] + 1;
                int next = now[0] + i;
                if (i == 0) {
                    time--;
                    next = 2 * now[0];
                }
                if (next > LIMIT) {
                    continue;
                }
                if (!visited.containsKey(next) || visited.get(next) > time) {
                    visited.put(next, time);
                    pq.offer(new int[]{next, time});
                }
            }

        }
        return NOT_FOUND;
    }
}