[코테 매일 풀기 14일차] 1124

백준 1753 최단경로

아이디어

• 간선을 저장하는 자료구조는 ArrayList[] list를 만들고, Edge class의 객체를 생성한다.
• Edge 클래스는 도착점과 가중치가 저장된다.
• dist[] 배열로 최소값 저장

1. dist 배열 선언 및 초기화 (Max value로 초기화) 
2. 우선순위 큐 선언 (가중치 기준 오름차순) 
3. 시작점을 pq에 넣기 (시작점, 거리)
3. 다익스트라 알고리즘 
- while (pq가 빌때까지): 
	//pq에서 현재 노드 꺼내기 
    //이미 처리된 노드면 continue
    if(현재까지의 거리 >  현재 거리) continue; 
    //현재 노드와 연결된 모든 간선 탐색 
    //더 짧으면 갱신 

	



```java
    static int V, E, K;
    static ArrayList<Edge>[] graph; //전역 변수
    static StringBuilder sb;

    public static void main(String[] args) throws IOException{
        input();
        solution(K);

    }
    static void solution(int start){//bfs처럼 생각
        //1. 거리 배열 선언 및 초기화
        int[] dist = new int[V+1];
        //dist를 무한대로 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);
        //dist[start] = 0
        dist[start] =0;

        //2. 우선순위 큐 선언( 가중치 기준 오름차순)
        PriorityQueue<Edge> pq = new PriorityQueue<>((a,b)-> a.w- b.w);

        //시작점 pq에 넣기
        pq.offer(new Edge(start, 0)); //번호: start, 거리: 0

        //출력
        while(!pq.isEmpty()){
            Edge cur = pq.poll();
            int curN = cur.v; //현재 정점
            int curD = cur.w; //현재 거리
            //이미 처리된 노드이면 continue ( 더 짧은 경로로 이미 갱신)
            if (curD > dist[curN]){
                continue;
            }
            //현재 노드와 연결된 간선 탐색
            for (Edge next: graph[curN]){
                int nextN = next.v;
                int nextD = curD + next.w;
                //더 짧은 경로 발견하면 갱신
                if(nextD < dist[nextN]){
                    dist[nextN] = nextD;
                    pq.offer(new Edge(nextN, nextD));
                }

            }
        }//while
        //출력
        sb = new StringBuilder();
        for (int i = 1; i <= V; i++){
            if(dist[i] ==Integer.MAX_VALUE){
                sb.append("INF\n");
            }else{
                sb.append(dist[i]).append("\n");
            }
        }
        System.out.println(sb);

    }