다익스트라. 최단경로

문제

일단 방향 그래프 문제이다. 주어지는 가중치는 10이하이고, 주어진 시작점으로부터 모든 정점까지의 최단경로를 출력한다.

해결방향성

가중치가 주어진 최단경로를 찾는 문제는, 다익스트라 알고리즘으로 해결할수있다.
1. Vertex 클래스에 가중치 변수를 하나 더 만든다.
: Vertex클래스 -> end(끝점), weight(가중치)
(사실, end라 쓰면 헷갈리니 그냥 num으로 두는게 좋을거같다.)
그리고, 이를 가져올 getter까지.
2. 그리고 간선의 개수가 20만개 이하이기 때문에, 인접행렬은 사용할수없다. 따라서 인접리스트로 구현한다.
3. 또한, 시간제한이 1초이기 때문에 O(logN)의 실행시간을 갖는 PriorityQueue를 Queue대신에 사용한다.

코드

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

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

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

    public int getEnd() {
        return end;
    }

    public int getWeight() {
        return weight;
    }

    // 가중치 최솟값 정렬 -> 사실 별의미없는듯 -> ㄴㄴ 없으면 안되는듯 : priorityQueue 정렬을 못함.
    @Override
    public int compareTo(Vertex1 o) {
        return this.weight - o.weight;
    }
}

public class Main {
    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 V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        disk = new int[V + 1];
        Arrays.fill(disk,Integer.MAX_VALUE);

        ArrayList<ArrayList<Vertex1>> graph = new ArrayList<>();
        graph.add(new ArrayList<>());
        for (int i = 1; i <= V; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            // 방향그래프
            graph.get(start).add(new Vertex1(end, weight));
        }

        BFSArrayList(graph, K);

        for (int i = 1; i <= V; i++) {
            if (i == K) { // 시작점의 최단거리 : 0
                bw.write(String.valueOf(0) + "\n");
            }
            else {
                if (disk[i] == Integer.MAX_VALUE) { // -1 : 끝까지 수정안됨 -> INF
                    bw.write("INF\n");
                } else { // 수정됨 : 최단거리 출력
                    bw.write(String.valueOf(disk[i]) + "\n");
                }
            }
        }


        bw.flush();
        br.close();
        bw.close();
    }
    private static int[] disk; // 최단경로 채우기
    private static void BFSArrayList(ArrayList<ArrayList<Vertex1>> graph, int K) {
        // Queue -> PriorityQueue
        PriorityQueue<Vertex1> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(new Vertex1(K, 0));

        while (!priorityQueue.isEmpty()) {
            Vertex1 poll = priorityQueue.poll();
            int pollNum = poll.getEnd(); // 시작점 추출
            int pollWeight = poll.getWeight();
            ArrayList<Vertex1> endVertexArrayList = graph.get(pollNum);
            if (endVertexArrayList.isEmpty()) {

            } else {
                for (Vertex1 endVertex : endVertexArrayList) {
                    int endVertexNum = endVertex.getEnd();
                    int endVertexWeight = endVertex.getWeight();
                    if (disk[endVertexNum] <= pollWeight + endVertexWeight) { // 갱신 필요 없음
                        // 그냥 continue;
                    } else {
                        // 갱신
                        disk[endVertexNum] = pollWeight + endVertexWeight;
                        priorityQueue.add(new Vertex1(endVertexNum, disk[endVertexNum]));
                    }
                    //key point: 갱신할때만 priorityQueue에 넣어줘서 중복을 줄여준다.
                }
            }
        }
    }
}

결론

1. Vertex 클래스에서는 그래프를 순회하면서 만나는 끝점의 수와, 가중치를 저장한다. -> 그리고 이를 static으로 선언해둔 최단경로를 기록한 disk[] 에 저장한다.
   또한, 중복을 순회를 막기위해 disk에 기록한 정점만을 priorityQueue에 넣어준다.
2. 인접리스트 구현
3. PriorityQueue 구현

결론적으로, BFS를 이용한 최단경로 구하기지만, 가중치를 비교해서 넣어주는 과정이 필요하다.