[백준] 13549 : 숨바꼭질 3 (JAVA)

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

 

🚩최단 경로

최단 경로 문제였고, 각 동작에 따른 가중치가 다르기 때문에(+1과 -1은 가중치가 1이고, *2는 가중치가 0) 다익스트라 알고리즘으로 접근하였습니다. 또한, 가중치가 낮은 순서대로 실행하기 위해 Queue 대신 우선순위 큐를 사용했습니다.

 

아래는 우선순위 큐로 제출한 코드입니다.

import java.io.*;
import java.util.*;

class Node {
    int num;
    int depth;

    public Node(int num, int depth) {
        this.num = num;
        this.depth = depth;
    }
}

class Main {

    static int K;
    static boolean[] visited;
    static int min = Integer.MAX_VALUE;

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

        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visited = new boolean[100_001];

        bfs(N, 0);

        bw.write(min + "");
        bw.close();
    }

    public static void djs(int num, int depth) {
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.depth - o2.depth);
        queue.add(new Node(num, depth));
        visited[num] = true;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            visited[now.num] = true;

            if (now.num == K) {
                min = Math.min(min, now.depth);
            }

            if (now.num * 2 <= 100_000 && !visited[now.num * 2]) {
                queue.add(new Node(now.num * 2, now.depth));
            }

            if (now.num + 1 <= 100_000 && !visited[now.num + 1]) {
                queue.add(new Node(now.num + 1, now.depth + 1));
            }

            if (now.num - 1 >= 0 && !visited[now.num - 1]) {
                queue.add(new Node(now.num - 1, now.depth + 1));
            }
        }
    }
}

 

---

🤔 Queue vs PriorityQueue

 

문제를 풀고 나서 생각해 보니, 우선순위 큐를 사용할 경우 순간이동 시 depth가 0이기 때문에 순간이동 경로를 모두 탐색한 후에 다음 경로가 진행된다는 점을 알게 되었습니다. 이런 상황에서는 일반 Queue를 사용하는 것도 좋은 방법일 것 같아, Queue로 코드를 다시 작성해 보고 PriorityQueue와 비교해 보았습니다.

 

아래는 Queue를 이용한 제출 코드입니다.

import java.io.*;
import java.util.*;

class Node {
    int num;
    int depth;

    public Node(int num, int depth) {
        this.num = num;
        this.depth = depth;
    }
}

class Main {

    static int K;
    static boolean[] visited;
    static int min = Integer.MAX_VALUE;

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

        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visited = new boolean[100_001];

        bfs(N, 0);

        bw.write(min + "");
        bw.close();
    }

    public static void bfs(int num, int depth) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(num, depth));
        visited[num] = true;

        while (!queue.isEmpty()) {
            Node now = queue.poll();

            if (now.num == K) {
                min = Math.min(min, now.depth);
            }

            if (now.num * 2 <= 100_000 && !visited[now.num * 2]) {
                queue.add(new Node(now.num * 2, now.depth));
                visited[now.num * 2] = true;
            }

            if (now.num - 1 >= 0 && !visited[now.num - 1]) {
                queue.add(new Node(now.num - 1, now.depth + 1));
                visited[now.num - 1] = true;
            }

            if (now.num + 1 <= 100_000 && !visited[now.num + 1]) {
                queue.add(new Node(now.num + 1, now.depth + 1));
                visited[now.num + 1] = true;
            }
        }
    }
}

 

Queue를 사용했을 때, 실행 시간이 더 빠르고 메모리 사용량도 더 적다는 점을 확인할 수 있었습니다!