본문 바로가기
algorithm

[JAVA] 백준 K번째 최단경로 찾기 1854 (다익스트라)

by onejunu 2022. 3. 12.

만약 다익스트라 알고리즘이 어떤거였는지 다시 상기해보려면 아래 링크 참고해주시기 바랍니다.

이번 문제는 다익스트라 개념을 응용한 쉽지 않은 문제였습니다. 메모리 제한과 더불어 속도제약이 까다로웠습니다.

 

https://onejunu.tistory.com/87

 

[JAVA] 백준 최단 경로 1753 ( 다익스트라 알고리즘)

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는..

onejunu.tistory.com

그래도 다익스트라에 대해 간단히 언급해보겠습니다. 우선순위 큐를 이용한 다익스트라 알고리즘을 설명하기 전에 Node를 설명해보겠습니다. (우선순위큐의 top 에는 출발점 기준으로 가장 거리가 작은 노드가 들어가 있습니다.)

 

여기서 우선순위큐에 들어가는 Node 다음과 같이 정의되어 있습니다. 출발점 기준으로 to 는 목적지 이며 dist 는 거리입니다.

예를 들어, to = 2 이고 dist = 10 이라면 출발점(문제기준으로 1번)에서 2번까지의 거리가 10이라는 의미입니다.

해당 노드는 인접리스트와는 다른 개념입니다. 인접리스트는 말그대로 노드간의 거리를 저장하는 리스트입니다. 하지만 제가 정의한 우선순위큐에 들어가는 Node는 단순 노드간의 거리가 아니라 출발점에서 to 까지 가는데 총 거리가 dist 인점을 유의하시기 바랍니다. 반면 인접리스트에 정의된 Node는 단순 노드간의 거리를 정의합니다. 같은 용어를 써서 헷갈릴 수 있습니다.

static class Node implements Comparable<Node>{
        int to;
        int dist;

        public Node(int to, int dist) {
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

 

우선순위 큐에서 꺼낸 노드는 출발점에서 to 까지 dist 거리를 가집니다. 그 노드를 cur 라고 합시다. 만약 cur를 방문한적이 있다면 큐에서 다시 꺼내는 것을 반복합니다. 그 다음 cur 와 연결된 인접리스트에서 노드를 가져옵니다. cur와 연결된 모든 노드를 현재 cur.dist 와 next.dist 를 더하여 새로운 노드를 아래와 같이 만들어 우선순위큐에 추가합니다. 

new Node(next.to,cur.dist + next.dist)

 

일반적으로 다익스트라 알고리즘은 처음 방문한 노드에 대해서 최단거리가 보장이 됩니다. 하지만 이번 문제는 노드는 항상 재방문 가능하다는 것입니다. 그러면 모든 경로를 구해서 k번째 최단거리를 구하면 되는 것도 아닙니다. 왜냐하면 메모리 초과가 납니다. 그러면 메모리를 최대한 덜 쓰기 위해서는 각 노드는 최대 k개의 최단거리를 보유하고 있으면 됩니다.

 

일반적인 다익스트라 알고리즘으로 로직을 진행하되 다른 부분이 하나 있습니다. 먼저 모든 노드에 대해 출발점에서 해당 노드까지의 거리를 저장할 dist 1차원 배열로 선언했던것과 달리 각각의 큐를 가져야 한다는 것입니다.

 

pq = Node 들에 대한 우선순위 큐

distQueue = 우선순위 큐 배열

static void kthDijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1,0)); // 1까지 가는데 0
        distQueue[1].add(0);

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

            for(Node next : adj[cur.to]) {
                // 갱신이 되었을 경우에만 pq 에 다음을 넣음
                if(distQueue[next.to].size() < k  || distQueue[next.to].peek() > cur.dist + next.dist
                ) {
                    if(distQueue[next.to].size() == k) distQueue[next.to].poll();
                    distQueue[next.to].add(cur.dist + next.dist);
                    pq.add(new Node(next.to,cur.dist + next.dist));
                }
            }

        }
    }

 

다익스트라 알고리즘과 똑같아 보이지만 다릅니다.  방문할 노드의 distQueue 사이즈가 k보다 작거나 distQueue 의 가장 큰 값이 갱신될 수 있는지 봐야합니다.  그러면 그냥 distQueue에 이때까지 계산된 거리인 cur 까지의 거리와 next 까지의 거리를 더한 값을 계속 추가해주면 됩니다. 전체 코드를 보면서 이해해보기 바랍니다.

 

package boj.P1854;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static Fs fs = new Fs();
    static int n,m,k;
    static ArrayList<Node>[] adj = new ArrayList[1001];
    static PriorityQueue<Integer>[] distQueue = new PriorityQueue[1001];
    static StringBuilder answer = new StringBuilder();
    public static void main(String[] args) throws Exception{
        input();
        kthDijkstra();
        makeAns();
    }

    static void kthDijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1,0)); // 1까지 가는데 0
        distQueue[1].add(0);

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

            for(Node next : adj[cur.to]) {
                // 갱신이 되었을 경우에만 pq 에 다음을 넣음
                if(distQueue[next.to].size() < k  || distQueue[next.to].peek() > cur.dist + next.dist
                ) {
                    if(distQueue[next.to].size() == k) distQueue[next.to].poll();
                    distQueue[next.to].add(cur.dist + next.dist);
                    pq.add(new Node(next.to,cur.dist + next.dist));
                }
            }

        }
    }

    static void makeAns() {
        for(int i=1;i<=n;i++) {
            if(distQueue[i].size() < k) answer.append(-1).append('\n');
            else answer.append(distQueue[i].peek()).append('\n');
        }

        System.out.println(answer);
    }



    static void input() throws Exception{
        n = fs.nInt();
        m = fs.nInt();
        k = fs.nInt();

        for(int i=0;i<=n;i++) {
            adj[i] = new ArrayList<>();
            distQueue[i] = new PriorityQueue<>(Collections.reverseOrder());
        }

        for(int i=0;i<m;i++) {
            int a = fs.nInt();
            int b = fs.nInt();
            int c = fs.nInt();
            // a -> b 까지 가는데 c
            adj[a].add(new Node(b,c));
        }

    }

    static class Node implements Comparable<Node>{
        int to;
        int dist;

        public Node(int to, int dist) {
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

    static class Fs{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nInt() throws Exception{
            if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }
    }
}

https://github.com/algorithmFor2021/wonjun_jo

 

GitHub - algorithmFor2021/wonjun_jo: BOJ 와 프로그래머스 알고리즘 풀이

BOJ 와 프로그래머스 알고리즘 풀이. Contribute to algorithmFor2021/wonjun_jo development by creating an account on GitHub.

github.com

 

댓글