다익스트라 기본문제

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

package 다익스트라;
    
import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.Scanner;
    
public class 최소비용구하기_1916 {
    static int E,V;//정점과 간선의 수
    static int[] arr;//각 정점에서 다음 정점까지의 최소 가중치 값을 저장하는 배열
    static boolean[] visit;//방문 배열
    static List<Node> list[];//각 정점에 연결된 정점과 가중치 값을 저장할 리스트 배열
    static int max=Integer.MAX_VALUE;//최대값
    
    //Node라는 클래스를 만들어 연결되는 정점과 연결될 때의 가중치 값을 저장할 클래스
    static class Node implements Comparable<Node>{
        int v;//연결될 값 그니까 시작 값이 아닌 끝 값
        int w;//가중치 값
        //멤버변수 선언
        public Node(int v, int w) {
            super();
            this.v = v;
            this.w = w;
        }
        //가중치 값으로 정렬해줌
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return this.w-o.w;
        }        
        
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        V=sc.nextInt();//정점 수        
        E=sc.nextInt();//가중치 값
        arr=new int[V+1];//1부터 시작할 것이기 때문에 저장해줄 배열도 정점의 수+1
        visit=new boolean[V+1];//1부터 시작할 것이기 때문에 저장해줄 방문 배열도 정점의 수+1        
        list=new ArrayList[V+1];//1부터 시작하기 때문에 리스트 배열도 정점의 수+1
        
        //인접 리스트 배열 안에 리스트 값들을 하나씩 ArrayList선언
        for (int i = 1; i <= V; i++) {
            list[i]=new ArrayList<>();
        }
        
        //각 시작값과 끝값 가중치 값 입력
        for (int i = 1; i <=E; i++) {
            int st=sc.nextInt();
            int ed=sc.nextInt();
            int w=sc.nextInt();
            
            //각 시작값에 끝값과 가중치 값을 더해 정점과 이어지는 정점과 가중치 값을 시작 값에 저장
            list[st].add(new Node(ed,w));
        }
        
        int start=sc.nextInt();//출발점 입력
        int end=sc.nextInt();//도착점 입력
        Arrays.fill(arr, max);//각 저장 배열에 정점들에 큰 값들 입력
        dijkstra(start);//다익스트라 알고리즘 시작
        System.out.println(arr[end]);
    }
    
    private static void dijkstra(int end) {
        PriorityQueue<Node> pq=new PriorityQueue<>();//다익에서 필수인 priorityQueue 선언
        pq.add(new Node(end,0));//pq큐에 처음에 만든 Node클래스에 끝값과 가중치 값인 객체를 만들고
        //그 객체의 끝 값과 가중치 값을 큐에 더해준다.
        arr[end]=0;//일단 while에 들어가기 전이기 때문에 첫 값이다.그래서 그 값을 0으로 바꿔준다.시작 점이라는 의미
        while (!pq.isEmpty()) {//이제 큐가 비기 전까지 즉 끝까지 반복
            Node now=pq.poll();//넣었던 값들 중 맨 앞에 있는 값을 꺼낸다(PriorityQueue)
            
            //여기서 이제 제일 중요
            //없으면 시간초과남
            //만약 이미 방문한 정점이면 그냥 밑에 반복들을 다 하지말자!
            //그래서 방문 안 한 노드만 검사하기 위해 그냥 continue때려 박아버리기
            if(visit[now.v]) continue;
            int End=now.v;//지금 들어온 정점의 번호           
           
            //int W=now.w;//지금 들어온 정점의 가중치 값 이 가중치 값은 지금까지 들어온 가중치 값의 최소값이다.
            visit[End]=true;
            //visit[end]=true;//입력되는 정점들은 다시 안 올 것이기 때문에 true로 바꿔 방문처리
            //지금 들어온 정점과 연결된 정점의 수 만큼 반복
            	for (int i = 0; i <list[End].size(); i++) {            	
                Node cur=list[End].get(i);//연결된 수 중 가중치 값이 가장 작은 정점의 번호와 가중치 값을 cur값에 저장
                int END=cur.v;//이제 now의 Node와 연결된 cur Node의 정점을 END에 저장
                int ww=cur.w;//역시  now의 Node와 연결된 cur Node의 가중치 값을 ww에 저장
                //만약 이제 확인하려는 정점이 이미 방문한 배열이 아니고
                //지금까지 저장된 최소값의 가중치와 지금 이어진 상태의 가중치의 합이 저장되어 있는
                //새로운 정점의 가중치 값보다 크다면
                if (!visit[END]&&arr[END]>arr[End]+ww) {                	
                	//그 값을 더 작은 값으로 초기화 해준다.
                    arr[END]=arr[End]+ww;
                    //그리고 그 노드의 끝점과 그 끝점의 최소 가중치 값을 큐에 다시 넣어준다.
                    pq.add(new Node(END,arr[END]));
                }
            }
        }
    }
}

노드의 끝값과 가중치 값을 받을 클래스를 하나 만들고 인접 리스트로 받기 위한 반복문을 해주고 역시 boolean의 방문 배열도 만들어줘야한다.

다익스트라 메서드에  priorityQueue를 선언해준다.

그리고 바로 그 시작점과 0 값을 큐에 넣고 while 반복문이 비지 않을 때까지 큐에서 가장 앞에 있는 값을 빼고 만약 뺀 값이 방문했던 정점이라면 continue를 하면서 시간을 줄인다. 이거 안해주면 바로 시간 초과 남. continue하면서 시간을 절약해주자.

확인할 노드의 정점을 저장하고 그 정점을 방문표시해준다.

그리고 확인할 정점과 연결되어 있는 정점들을 확인해줄 반복문을 연결된 정점의 수만큼 for문을 작성한다.

그 반복문 안에는 연결된 정점의 번호와 거기까지의 가중치 값이고 만약 그 정점이 방문하지 않은 정점이고 지금까지의 가중치 값의 최소값과 연결된 가중치의 합이 연결된 정점의 가중치값의 최소값보다 작다면 지금까지의 가중치 값과 연결된 가중치의 합으로 바꿔준다.

그리고 그 정점과 그 정점의 가중치 값을 큐에 바로 넣어준다.