백준 1753번 : 최단경로 java

이 문제는 다익스트라 알고리즘을 푸는 문제입니다.

이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다.

저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입력하였습니다.

그러나 이 방식을 이용하면 정점의 개수가 최대인 20,000개일 때 20,000 * 20,000 * 4byte = 1,600,000,000byte
즉 이 2차원 배열을 int형으로 선언하는 데만도 1.6GB라는 어마어마한 메모리를 사용한다는 것을 알게 되었습니다.

따라서 이 문제를 다른 방식으로 풀 수 있나를 찾아보니 우선순위 큐를 이용하여 문제를 푸는 방법이 있어서 이 방법을
이용하여 다익스트라 알고리즘을 구현하였습니다. 문제를 푼 방법은 코드를 보면서 추가로 설명드리겠습니다.

---

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

public class Main{
    static ArrayList[] l;
    static int[] dist;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine()) - 1;

        l = new ArrayList[V];
        dist = new int[V];

        for(int i = 0; i<V; i++) {
            l[i] = new ArrayList<Node>();
            dist[i] = Integer.MAX_VALUE;
        }

        for(int i = 0; i<E; i++){
            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            int w = Integer.parseInt(st.nextToken());

            l[u].add(new Node(v, w));
        }

        dijkstra(K);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<V; i++){
            if(dist[i] == Integer.MAX_VALUE)
                sb.append("INF").append("\n");
            else
                sb.append(dist[i]).append("\n");
        }

        System.out.print(sb);
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.add(new Node(start, 0));

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

            int len = l[now.v].size();
            for(int i = 0; i<len; i++){
                Node next = (Node)l[now.v].get(i);

                if(dist[next.v]>now.w + next.w){
                    dist[next.v] = now.w + next.w;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }
}

class Node implements Comparable<Node>{
    int v, w;

    public Node(int v, int w){
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Node n){
        return this.w - n.w;
    }
}

저는 이 문제를 풀 때 ArrayList의 배열을 이용하였습니다. 2차원 배열을 선언할 수는 없기 때문에 이와 비슷한 효과를
내려면 어떻게 해야 할까를 생각해보았습니다.

우선 저는 LinkedList를 생각하였습니다. 따라서 이로 이 문제를 구현하였고 시간 초과라는 결과가 나왔습니다.

왜 LinkedList를 사용하면 시간 초과가 나오지? 라는 생각을 저는 하였고 이에 대해서 더 찾아보았습니다.

찾아본 결과 LinkedList는 저장될 때 각 노드들이 포인터로 연결되어 있고 ArrayList는 메모리 상에 연속된 공간에
저장된다는 것을 알았습니다. 따라서 이러한 저장 방식의 차이 때문에 아래의 표와 같은 시간 차이가 생기는 것이었습니다.

따라서 저는 LinkedList를 전부 ArrayList로 바꿔주었습니다.

저는 ArrayList[]의 각 항을 각각의 정점을 의미한다고 생각하였습니다.

ArrayList[0]은 0에서 시작하는 간선들의 모임, ArrayList[2]는 2에서 시작하는 간선들의 모임 이렇게 두었습니다.

따라서 2 3 4와 같은 입력값이 주어질 때 저는 1번 인덱스에서 시작해서 2번 인덱스로 가는 4의 가중치를 가진
간선이라고 간주하였고, ArrayList[1].add(new Node(2, 4))와 같이 처리하였습니다.

이것을 예제 1번을 예시로 설명드리도록 하겠습니다.

문제에서 V의 값이 5이니 5개의 배열을 만들어주었습니다. 각각의 칸에는 ArrayList가 들어있습니다.

이제 E가 6이 주어졌으니 6개의 간선을 추가해주겠습니다.

예제의 입력값을 다 넣으면 다음과 같은 그림이 됩니다. 각 셀의 앞 숫자는 v, 뒤의 숫자는 가중치 즉 w를 의미합니다.

입력값보다 u, v에서 -1을 해준 이유는 idx를 그렇게 설정하였기 때문입니다.

입력값을 그대로 쓰시려면 ArrayList 배열을 1칸 더 만드셔서 사용하셔도 됩니다.

이렇게 ArrayList 배열을 만들면 이제 dijkstra 함수를 실행합니다.

다익스트라 알고리즘은 아래의 링크에 자세히 설명이 되어있습니다.

백준 1916번 : 최소비용 구하기 java

다익스트라 알고리즘을 구현할 때 PriorityQueue를 이용한 이유는 시작점에서 가장 가중치가 적은 인덱스로 바로 가기
위해서입니다.

PriorityQueue에 Node들이 들어가면 그것들이 가지고 있는 w에 따라서 정렬이 되고 가장 작은 w를 가지고 있는 Node부터 처리하기 위해서 PriorityQueue로 정렬하여 사용하였습니다.

int len = l[now.v].size();
for(int i = 0; i<len; i++){
    Node next = (Node)l[now.v].get(i);

    if(dist[next.v]>now.w + next.w){
        dist[next.v] = now.w + next.w;
        pq.add(new Node(next.v, dist[next.v]));
    }
}

위의 코드는 ArrayList[]안의 자료들을 이용하여 dist[]의 값을 바꿔주는 코드입니다.

ArrayList[]의 각각의 칸 안에 있는 Node들은 그 정점에서 시작하는 간선들입니다. 이것들을 next라는 변수에 담아서 

if(dist[next.v]>now.w + next.w)

즉 시작점에서 next까지 바로 가는 것과 시작점에서 now를 거쳐서 next까지 가는 것의 가중치를 비교하여서 dist를
입력하였습니다.