[JAVA] 백준 최단 경로 1753 ( 다익스트라 알고리즘)

www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

자바는 기본적으로 우선순위 큐는 최소힙으로 구현되어 있다.

 

알고리즘은 아래와 같다.

 

1. 다익스트라 알고리즘

 

준비물 : dist 배열 (출발점에서 각 지점까지 최단거리 배열 초기는 모든 값이 INF )  / visited 배열 / 인접리스트 or 인접행렬 등 그래프 간의 가중치를 알 수 있어야 함.

 

1. 우선순위큐 (최소힙) 생성

2. 출발 정점 dist는 0 으로 초기화

3. 큐에 출발정점을 넣는다.

 

4. 큐가 비어있지 않다면 무한 반복

    4-1. 큐에서 하나 꺼냄 (cur)

    4-2. 큐에서 꺼낸 정점(visited[cur]==true?)을 방문한 적이 있다면 continue

    4-3. 방문한 적이 없다면 ?(visited[cur] == false)

        4-3-1. 꺼낸 정점과 연결된 모든 정점을 가져온다.

        4-3-2. 연결된 모든 각각의 정점을 next 노드라고 할때, 연결된 모든 정점에 대해 다음을 수행한다.

            4-3-2-1. 현재 정점까지 거리(dist[cur]) + 현재 정점에서 꺼낸 정점까지의 거리 (next.가중치값) < dist[next] 이면 dist[next]를 갱신

            4-3-2-2. 갱신했다면 큐에 next노드를 넣음.

 

 

 

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

class Main{
    static int n;
    static int m;
    static int start;
    static int[] dist;
    static boolean[] visited;
    static ArrayList<ArrayList<Node>> list = new ArrayList<>();

    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());


        // n , m , start input!
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());
        dist = new int[n+1];
        Arrays.fill(dist,987654321);
        visited = new boolean[n+1];
        for(int i=0;i<n+1;i++){
            list.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            int a,b,c;
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Node(b,c));

        }


        dijkstra(start);

        for(int i=1;i<=n;i++){
            System.out.println(dist[i]==987654321?"INF":dist[i]);
        }

        bw.flush();
        br.close();
        bw.close();
    }

    static void dijkstra(int start){
        dist[start] = 0;
        Node node = new Node(start,0);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(node);

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            int to = cur.to;
            int time = cur.time;


            if(visited[to]) continue;
            else{
                visited[to] = true;
                ArrayList<Node> nextList = list.get(to);

                for(int i=0;i<nextList.size();i++){
                    Node temp = nextList.get(i);
                    if(dist[temp.to] > dist[to] + temp.time){
                        dist[temp.to] = dist[to] + temp.time;
                        pq.add(new Node(temp.to,dist[temp.to]));
                    }
                }
            }

        }
    }

    static class Node implements Comparable<Node>{
        int to,time;
        public Node(int to,int time){
            this.to = to;
            this.time = time;
        }

        @Override
        public int compareTo(Node o) {
            return this.time - o.time;
        }
    }

}