[백준]13549 - 숨바꼭질 3 문제 풀이(Java,자바)

문제

13549번: 숨바꼭질 3

 

들어가며

최소 비용인데 겉으로 볼 때 뭔가 bfs, 다익스트라를 써야할 것 같지 않아서 여기저기 헤매다가 결국 못 풀었습니다.

근데 bfs, 다익스트라더라고여.

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, k;
    static boolean[] visited;
    static int MAX = 100000;

    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());
        visited = new boolean[MAX + 1];

        System.out.println(search());
    }

    private static int search() {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.time, b.time)); // 시간 기준 오름차순 정렬
        pq.offer(new Node(n, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (node.x == k) {
                return node.time; // 목표 위치 도달 시 최소 시간 반환
            }

            if (visited[node.x]) {
                continue; // 이미 방문한 위치는 스킵
            }

            visited[node.x] = true;

            // 순간이동 (가중치 0)
            if (node.x * 2 <= MAX && !visited[node.x * 2]) {
                pq.offer(new Node(node.x * 2, node.time));
            }

            // 뒤로 이동 (가중치 1)
            if (node.x - 1 >= 0 && !visited[node.x - 1]) {
                pq.offer(new Node(node.x - 1, node.time + 1));
            }

            // 앞으로 이동 (가중치 1)
            if (node.x + 1 <= MAX && !visited[node.x + 1]) {
                pq.offer(new Node(node.x + 1, node.time + 1));
            }
        }

        return -1; // 이 코드는 실행되지 않음 (문제의 조건 상 항상 목표에 도달 가능)
    }

    static class Node {
        int x;
        int time;

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

 

다익스트라를 이용해서 풀었습니다.

이때, 가중치를 두는 것이 중요합니다.

 

먼저 시간을 아낄려면 아예 시간이 안드는 x*2를 많이 해야 합니다.

그렇기 때문에 제일 먼저 큐에 넣어줍니다

(큐는 먼저 들어간 순서대로 나오기 때문)

그 다음에 넣을 것은 뒤로 한 칸 이동하는 겁니다.

왜 이게 우선 순위가 되냐면 값이 낮아져야 x*2가 나올 가능성이 높기 때문입니다.

 

5-10-9-18-17

 

만약 10에서 11로 갔다면 최단 시간을 구할 수 있었을까요??

문제의 요점은 어떻게든 x*2를 진행해야 합니다.

그래서 -1이 +1보다 먼저 왔다고 생각하시면 됩니다.