[백준1753] 최단경로

📎 문제링크

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

📄 문제설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

📝 문제풀이

기초적인 dijkstra 문제
ArrayList로 인접 노드를 연결하고 dijkstra는 priority queue로 만들었다
dijkstra를 priority queue로 만든이유는
dijkstra의 시간복잡도는 O(V^2) ---> 모든정점을 확인(v)*그중 최소인 것을 확인 (v)
인데priority queue를 사용하면 모든 간선이 한번씩 검사된다는 점에서 첫 번째 작업이 O(V), 각 간선마다 우선수위 큐에 자료가 삽입 연산이 일어난다는 점에서 O(VlogV)이며, 이 둘을 합쳤을 때, (V+VlogV)의 시간복잡도는 O(VlogV)가 되기 떄문이다.

💡 Code

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.ArrayList;

public class main {

    static int n,e;
    static int k;
    static ArrayList<int[]>adj[];// 인접 노드 배열
    static int dis[]; // 최소 경로 배열
    public static void main(String[]args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k =Integer.parseInt(br.readLine());
        adj=new ArrayList[n+1];
        dis=new int[n+1];
        // adj 초기화
        for (int i = 1; i <=n; i++) {
            adj[i]=new ArrayList<int[]>();
        }
        // adj list 에 값 저장
        for (int i = 1; i <= e; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken()); // 츨발
                int v = Integer.parseInt(st.nextToken());  //도착
                int w = Integer.parseInt(st.nextToken()); // 가중치
                adj[u].add(new int[]{v,w}); // u 노드 마다 인접 노드 연결
        }
        dijkstra();
        StringBuilder sb= new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if(dis[i]!=Integer.MAX_VALUE) {
                sb.append(dis[i]+"\n");
            }
            else sb.append("INF"+"\n");
        }

     System.out.println(sb);
    }

    private static void dijkstra(){
        PriorityQueue<Node>pq=new PriorityQueue<Node>();
         //dis배열 INTEGER.MAX_VALUE 무한대 초기화
       /* for (int i = 0; i <=n; i++) {
            dis[i]= Integer.MAX_VALUE;
        }*/
        Arrays.fill(dis, Integer.MAX_VALUE);
        //1. 초기노드 설정-초기화
        dis[k]=0;
        pq.add(new Node(k,0));  // 첫 노드 pq 삽입
        while(!pq.isEmpty()){// pq가 비어 있지 않으면
           Node current= pq.poll();
          if(current.weight>dis[current.vertex]) continue; // 최솟값이 아니면 알고리즘 실행x
            //2. 방문하지 않은 노드중 가장 비용이 적은 노드 선택
            for (int follow[]:adj[current.vertex]) {
                if(dis[follow[0]]>dis[current.vertex]+follow[1]) {
                 //3. 해당 노드로부터 갈수 있는 노드들의 비용 갱신 
                       dis [follow[0]] = dis[current.vertex] + follow[1];
                       pq.add(new Node(follow[0],dis[follow[0]]));
                }
               
            }


        }

    }

        public static class Node implements  Comparable<Node> {
            int vertex;
            int weight;

            Node(int vertex, int weight) {
                this.vertex = vertex;
                this.weight = weight;
            }

            @Override
            public int compareTo(Node o) {
                return weight - o.weight;

            }

        }


}

👍 Comment