[BOJ] 백준 1753 - 최단경로 (자바)

다익스트라.

맨처음 인덱스 x 인덱스로 했다가 런타임에러.. 메모리 초과 떴다.

20000 * 20000 이므로 400000000 ... 4억이다. 메모리 안되서 땡.

어떻게 짤까 고민하다가 클래스 하나 만들어서 구현했는데

왠걸 시간초과.... 어디서 잘못됬나 봤더니 vertex의 예전값과 비교하는데 더 좋을 경우만 바꾸면 되는데 그렇지 않을 경우도 계속 Queue에 집어넣어서 실패...

다시 구현했는데 연속 3번 틀렸습니다. 문구가 뜨네? 진짜 어디서 틀린지 몰라서 우선순위 큐가 MaxHeap으로 되어야 하나 이생각했는데

틀린부분 찾으니까 내가 부등호 잘못해준곳이 있었네? 음... 아무튼 구현 성공.

확실히 개념 공부하는데는 코딩으로 배우는게 최고긴 하네

풀이

1. 거리를 계산할 distance[] 배열 하나, vertex간 연결과 edge를 저장해줄 Edge클래스와 Arraylist[] 배열 하나, INF를 구별해줄 visited[] 하나 있으면 된다.

2. 출발점으로부터 그 다음값들을 큐에 저장해준다. 가장 Edge가 짧은 노드들로 정렬하는게 성능이 좋단다. 그래서 우선순위 큐를 사용하는 거고. (난 안했네;;)

3. 다음값들을 큐에 저장하기 전에 이전값이 더 작다면(거리가 가깝다면) 굳이 큐에 집어넣어줄 필요 없다.

4. 큐가 빌 때까지 반복하면 끄으읏!

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(newInputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int vertex = Integer.parseInt(str[0]);
        int edge = Integer.parseInt(str[1]);
        int K = Integer.parseInt(br.readLine());
        int[] distance = new int[vertex + 1];
        // 방문하지 못한점은 INF로 출력해줘야한다.
        boolean[] visited = new boolean[vertex + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        // index by index 배열로 했더니 메모리 초과 나서 ArrayList로 바꿈.
        ArrayList<Edge>[] list = new ArrayList[vertex + 1];
        for (int i = 0; i <= vertex; i++) {
            list[i] = new ArrayList<Edge>();
        }
 
        for (int i = 0; i < edge; i++) {
            str = br.readLine().split(" ");
            list[Integer.parseInt(str[0])].add(new Edge(Integer.parseInt(str[1]), Integer.parseInt(str[2])));
        }
 
        // 우선순위 큐를 사용해야 한다. 성능이 더 좋아짐
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        // 시작점 설정해주고 시작점 - 시작점 거리는 0이다.
        q.add(K);
        distance[K] = 0;
        while (!q.isEmpty()) {
            // 다음에 방문할 vertex 설정
            int current = q.poll();
            // 방문했기 떄문에 true, INF는 아니다.
            visited[current] = true;
 
            for (int i = 0; i < list[current].size(); i++) {
                // 현재 vertex에서 다음 vertex를 차근차근 비교해서 우선순위 큐에 넣어야한다.
                int next = list[current].get(i).end; // 다음 vertex
                int value = list[current].get(i).value; // 현재 - 다음 간 edge값
 
                // 이전에 있던 값이 더 크다면 굳이 다시 방문할 필요가 없다. 이미 그 전이 더 최단 경로이기 때문에
                if (distance[next] > distance[current] + value) {
                    distance[next] = Math.min(distance[next], value + distance[current]);
                    q.add(next);
 
                }
 
            }
        }
        // 출력
        for (int i = 1; i <= vertex; i++) {
            if (visited[i]) {
                System.out.println(distance[i]);
            } else {
                System.out.println("INF");
            }
        }
    }
 
}
 
class Edge {
    int end;
    int value;
 
    Edge(int end, int value) {
        this.end = end;
        this.value = value;
    }
}