Cooper's devlog

[문제 설명]

말그대로 최단거리를 구하는 문제입니다.

그렇다면 최단거리는 어떻게 구해야 하는걸까요?

최단거리를 구하기 위해서는 다익스트라(dijkstra) 알고리즘에 대해 알고 있어야 합니다!

문제 풀이에 들어가기에 앞서 다익스트라에 대해 간략히 설명드리고 문제를 풀어보도록 하겠습니다.

[다익스트라 알고리즘]

다익스트라(dijkstra) 알고리즘은 다이나믹(dp) 프로그래밍을 활용한 최단 경로(Shortest Path) 알고리즘 입니다.

특정한 하나의 정점을 기준으로 해서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.

다만 '음의 간선을 포함할 수 없다'는 점을 유의하세요!

자세한 문제 접근 방법은 해당 문제를 예로 들어서 설명하도록 하겠습니다.

[문제 접근 방법]

자 이제 시작해보도록 하겠습니다!

다익스트라 알고리즘을 풀이하는 순서는 아래와 같습니다.

(1) 모든 경로의 최단 거리를 무한대(INF)로 초기화 한다.

(2) 시작 지점 노드의 거리를 0으로 초기화하고 방문여부를 체크한다.

(3) 각 노드를 탐색하여 최단 거리를 구한다.

아니 저기 너무 간략히 정리한 것 아니야?! 라고 말씀하실 수도 있으실텐데요.

맞아요 저게 답니다;;ㅋㅋ

아래에 세부 코드로 더욱 설명하도록 하겠습니다.

[전체코드]

자세한 설명이 필요하시다면 아래에 [세부코드]를 확인해주세요.

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

class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

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

        int nodeSize = Integer.parseInt(st.nextToken());
        int edgeSize = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(br.readLine());

        Graph graph = makeGraph(nodeSize, edgeSize);

        graph.dijkstra(start);
    }

    private static Graph makeGraph(int nodeSize, int edgeSize) throws IOException {
        Graph graph = new Graph(nodeSize);

        while (edgeSize-- > 0) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            graph.insertNode(start, end, weight);
        }

        return graph;
    }

}

class Graph {
    class Node implements Comparable<Node> {
        int end;
        int weight;

        public Node(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return this.weight - other.weight;
        }
    }

    private ArrayList<Node>[] edgeList;

    public Graph(int size) {
        this.edgeList = new ArrayList[size + 1];
        for (int index = 0; index <= size; index++) {
            edgeList[index] = new ArrayList<>();
        }
    }

    public int size(){
        return this.edgeList.length - 1;
    }

    public void insertNode(int start, int end, int weight){
        this.edgeList[start].add(new Node(end, weight));
    }

    public void dijkstra(int start){
        boolean[] visited = new boolean[size() + 1];
        int[] distance = initDistance(size() + 1, start);

        distance = minDistance(distance, visited, start);

        print(distance);
    }

    private int[] minDistance(int[] distance,
                              boolean[] visited,
                              int start) {

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()){
            Node currentNode = pq.poll();
            int adjacent =  currentNode.end;

            if(!visited[adjacent]){
                visited[adjacent] = true;
            }else{
                continue;
            }

            for (Node node : edgeList[adjacent]){
                if(distance[node.end] > distance[adjacent] + node.weight){
                    distance[node.end] = distance[adjacent] + node.weight;
                    pq.offer(new Node(node.end, distance[node.end]));
                }
            }
        }

        return distance;
    }

    private void print(int[] distance) {
        final int INF = Integer.MAX_VALUE;

        for (int index = 1; index <= size(); index++){
            if(distance[index] == INF){
                System.out.println("INF");
            }else{
                System.out.println(distance[index]);
            }
        }
    }

    private int[] initDistance(int size, int start) {
        int[] distance = new int[size + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        return distance;
    }
}

[세부 코드]

1. dijkstra method :  알고리즘의 전체를 설명하는 메소드

    public void dijkstra(int start){
        boolean[] visited = new boolean[size() + 1];
        int[] distance = initDistance(size() + 1, start);

        distance = minDistance(distance, visited, start);

        print(distance);
    }

다익스트라 알고리즘을 사용하기 위해서는 두 배열이 필요합니다.

• boolean[]  visited: 해당 노드의 방문 여부를 확인하기 위한 배열
• int[] distance : 해당 노드까지의 최단 거리를 저장하는 배열

distance 배열은 initDistance 메소드의 결과를 반환하게 됩니다.

이 부분이 앞 부분에 설명드린 

(1) 모든 경로의 최단 거리를 무한대(INF)로 초기화 한다.

(2) 시작 지점 노드까지의 최단거리를 0으로 초기화하고,_____________________

부분에 해당하는 부분이고,

minDistance() 부분이

(2) 시작 지점 노드_____________________________________, 방문여부를 체크한다.

(3) 각 노드를 탐색하여 최단 거리를 구한다.

부분에 해당하는 부분입니다.

2. initDistance : 최단거리 배열 무한대(INF)초기화 + 시작지점 노드의 최단 거리 0 초기화

    private int[] initDistance(int size, int start) {
        int[] distance = new int[size + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        return distance;
    }

앞서 설명드린 것처럼 는 최단거리를 무한대(INF)로 초기화 하고 시작 지점 노드까지의 최단 거리를 0으로 초기화합니다.

(1) 우선 배열을 생성하고,

(2) 모든 배열의 요소에 무한대 값을 초기화 합니다.

(이 문제에서는 INF를 Integer.MAX_VALUE로 처리하였습니다.)

(3) distance[start] = 0을 시작지점을 0으로 초기화 하였습니다.

3. minDistance(distance, visited, start) : 해당 지점까지의 최단 거리를 구하는 메소드

이 부분이 다익스트라 알고리즘의 핵심 부분이니 주의깊게 봐주세요!!

먼저 사용하는 자료구조를 선택하는 방법이 중요합니다.

첫번째는 우선순위큐(PriorityQueue)를 사용하는 것입니다.

우선순위 큐를 사용하기 위해서는 이전에 ArryList배열을 생성해서 노드에 대한 정보를 저장해야 합니다.저장한 정보를 우선순위 큐에 저장 후, 최단 거리 로직을 구현하는 것이 이 문제의 핵심입니다.

두번째는 이차원 배열을 사용하는 것입니다.

이차원 배열의 인덱스를 이용해서 간선의 가중치를 입력한 후, 이 정보를 이용해서 최단 거리 로직을 구현합니다.

하지만 이 문제를 해결하기 위해서는 이차원 배열을 사용하게 되면 메모리 초과로 인해 결과에 빨간불이 뜰 것입니다.

그 이유는 문제에서 제공하는 메모리 제한이 128MB이기 때문입니다.

문제의 정점의 최대 갯수는20,000 입니다.

이차원 배열을 사용 시, 배열의 공간복잡도는 O(n^2) 이며,

할당 메모리는 20000 × 20000×4(byte) / 1024(byte/KB) / 1024(KB/MB) = 1155MB로 주어진 메모리를 초과합니다. 

그러므로 해당 문제에서 이차원 배열을 사용하는 것은 적합하지 않습니다.

(우선순위 큐를 사용할 경우, 공간 복잡도가 O(n)입니다.)

그러므로, 이번 문제에서는 노드를 요소로한 우선순위큐(PriorityQueue)를 사용합니다.

    private int[] minDistance(int[] distance,
                              boolean[] visited,
                              int start) {

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()){
            Node currentNode = pq.poll();
            int adjacent =  currentNode.end;

            if(!visited[adjacent]){
                visited[adjacent] = true;
            }else{
                continue;
            }

            for (Node node : edgeList[adjacent]){
                if(distance[node.end] > distance[adjacent] + node.weight){
                    distance[node.end] = distance[adjacent] + node.weight;
                    pq.offer(new Node(node.end, distance[node.end]));
                }
            }
        }

        return distance;
    }

보신는 것과 같이 코드에서는 우선순위큐(PriorityQueue)를 사용하는 것을 확인할 수 있습니다.

(아래에 Node에 대한 코드를 달아두었습니다.)

먼저 로직부터 설명을 드리면

(1) 우선순위큐에 시작점의 Node를 추가하고,

(2) 최근 노드를 반환하여 방문여부를 체크합니다 

(3) 노드 내에 연결지점(end)의 리스트들을 탐색하여 최소값을 갱신하도록 합니다.

[Node에 관한 설명]

    class Node implements Comparable<Node> {
        int end;
        int weight;

        public Node(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return this.weight - other.weight;
        }
    }

int end : 연결된 지점에 대한 정보를 담습니다.

int weight : 연결된 길이의 가중치를 담는 변수 입니다.

PriorityQueue는 객체를 요소할 때, 비교하는 기준을 정해야 하므로,

Comparable을 implemnet 받아 compareTo로 weight의 오름차순으로 정렬했습니다.

[결과]

처음에는 이차원 배열을 사용하여 메모리 초과가 발생했지만 우선순위큐를 사용해서 정답을 출력하는 것을 확인할 수 있었습니다!

다음에 이차원 배열을 사용하는 다익스트라 문제를 풀이하게 되면 다시 한번 찾아뵙겠습니다.

감사합니다:)