다익스트라 알고리즘 구현.md

다익스트라 알고리즘 구현 (최단거리)

import java.util.Scanner;
import java.util.ArrayList;

public class Main {

    // 입력 첫줄 뜻.
    // 8 11 0 6
    // 8: 정점, 11: 간선, 0: 시작점, 6: 끝점 
    // 즉, 0~6까지 가는데 최단거리를 알고 싶다는 것이다.

    // T[i] : 정점 i에 도달하는데 걸리는 최단거리
    
    // (1) T(i) 중 최솟값을 정한다. 단, 지금까지 최솟값으로 뽑히지 않았던 값들 중.
    // (2) indext로 부터 뻗어나간다. T[index] + cost

    static final int MAX = 100;
    static ArrayList<Integer>[] graph = new ArrayList[MAX];
    static ArrayList<Integer>[] cost = new ArrayList[MAX]; // 가중치를 알아보기 위한 변수
    static int[] Table = new int[MAX]; // 다익스트라 알고리즘 구현을 위한 배열

    static boolean[] check = new boolean[MAX];
    // check 배열에 관한 설명.
    // check[i] = true : 이미 i는 최단거리가 확정 되었다.
    // check[i] = false : 아직 i는 최단거리가 확정되지 않았다.

    static int n, m, start, end;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        for(int i = 0; i < MAX; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for(int i = 0; i < MAX; i++) {
            cost[i] = new ArrayList<Integer>();
        }
        
        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();
        end = sc.nextInt();

        for(int i = 0; i < m; i++) {
            int a, b, c;

            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();

            // c는 뭔가??
            // a ---- b 가 간선으로 연결 되어 있는데,
            // a --(c)-- b 간선의 가중치를 말하는 것이다.

            graph[a].add(b);
            graph[b].add(a);

            cost[a].add(c);
            cost[b].add(c);

            // cost 설명
            // 예를 들어, graph[1] 의 인접 리스트는 2 6 8 9 라고 생각해보자.
            // 무슨 말인가? 1과 연결되어 있는 정점들이 2 6 8 9 라는 말이다.

            // 그렇다면 cost[1] : 1 1 3 9 라고 생각해보자.
            // 전체적으로 설명 하자면,
            // 1정점과 2정점가 연결되어 있는데, 그때 간선의 가중치는 1이라는 말이다.
            // 또 보자면, 1정점과 8정점이 연결되어 있는데, 그때 간선의 가중치는 3이다.

            // 이렇게 까지 한다면 그래프를 저장 한것이다.
        }

        for(int i = 0; i < n; i++) {
            Table[i] = 987987987; // 처음 해당 정점의 최단거리 무한 -> 이유는? 아직 모르기 때문
            Table[start] = 0; // 초기값은 0이라고 채워 넣는다.
        }

        for(int i = 0; i < n; i++) {
            // 1) 최솟값을 구한다. 단, 지금까지 최단거리로 확정되지 않았던 정점에 대해서
            // 2) 그 최솟값을 갖는 노드로 부터 뻗어나간다
            // 이렇게 두개 구현하면 되는 것이다.

            int minValue = 987987987;
            int minIndex = -1;

            for(int j = 0; j < n; j++) { 
                // 여기서 루프를 돌면서 최솟값을 구하는 것이다.
                // 단, check 를 보면서 false인 애들만 고려를 해서 구한다.
                // false 라는 것은 최단거리가 확정되지 않앗다는 이야기 때문이다.

                if(!check[j] && minValue > Table[j]) { // !check 뜻은 부정으로 만드는 것이다.
                    // 설명하자면, 아직까지 최단거리가 확정되지 않는 친구들에 대해서 (=!check[j])
                    // 최솟값과 그때의 정점 번호를 기억하는 것이다.

                    // 아직 최단거리가 확정되지 않은 친구들에 대해서 
                    // 최소값과 그 정점의 번호를 기억하는 것이다.
                    minValue = Table[j];
                    minIndex = j;
                } 
                    
            }

            check[minIndex] = true; // 최단거리 확정 한다는 뜻이다.
                
            for(int j = 0; j < graph[minIndex].size(); j++) {
                int Node2 = graph[minIndex].get(j);
                int Cost2 = cost[minIndex].get(j);

                // minIndex ---(Cost2)--- Node2
                // 즉, 노드까지 다이렉트로 가는 방법도 있지만,
                // 돌아가는게 더 좋은 방법일 수도 있기 때문에 하는 것이다.

                if(Table[Node2] > Table[minIndex] + Cost2) {
                    Table[Node2] = Table[minIndex] + Cost2;
                }
            }
        }

        System.out.print(Table[end]);

    }
}