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

1. 문제

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

1753번: 최단경로

 

2. 풀이

방향그래프가 주어질 때 한 시작점에서 다른 모든 정점으로의 최댄 경로를 구하는 문제이다.

다익스트라 알고리즘으로 문제를 풀 수 있다. 다익스트라 알고리즘은 PriorityQueue를 사용한다 !

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int V,E, start;
    static int[] dis;
    static boolean[] visit;
    static ArrayList<Edge>[] adj;

    static class Edge{
        int v; // 도착 정점
        int c; // 비용
        public Edge(int v,int c){
            this.v=v;
            this.c=c;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        V=Integer.parseInt(st.nextToken()); // 정점개수
        E=Integer.parseInt(st.nextToken()); // 간선개수
        start=Integer.parseInt(br.readLine()); // 시작 위치

        // 간선 입력 받기 + 인접 리스트
        adj=new ArrayList[V+1];
        for(int i=0;i<=V;i++){
            adj[i]=new ArrayList<Edge>();
        }
        for(int i=0;i<E;i++){
            st=new StringTokenizer(br.readLine());
            int s=Integer.parseInt(st.nextToken());
            int e=Integer.parseInt(st.nextToken());
            int c=Integer.parseInt(st.nextToken());
            adj[s].add(new Edge(e,c));
        }

        // 경로 비용 저장하는 배열 - 무한대로 초기화
        dis=new int[V+1];
        for(int i=1;i<=V;i++){
            dis[i]=Integer.MAX_VALUE;
        }
        visit=new boolean[V+1];
        // 다익스트라
        dijkstra();
        // 정답 출력
        StringBuilder sb=new StringBuilder();
        for(int i=1;i<=V;i++){
            if(dis[i]==Integer.MAX_VALUE){
                sb.append("INF");
            }else {
                sb.append(dis[i]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static void dijkstra(){
        // Comparator : 람다 -> 가중치 작은 순서로 정렬
        PriorityQueue<Edge> pq=new PriorityQueue<>((o1, o2) -> o1.c - o2.c);
        dis[start]=0;
        pq.offer(new Edge(start,0));

        while(!pq.isEmpty()){
            Edge now=pq.poll();
            if(visit[now.v])
                continue;
            visit[now.v]=true;
            for(Edge e : adj[now.v]){ // 현재 정점에서 갈 수 있는 정점&비용 탐색
                if(!visit[e.v] && dis[now.v] + e.c < dis[e.v]){ // 최소 비용으로 방문
                    dis[e.v]=dis[now.v]+e.c;
                    pq.offer(new Edge(e.v, dis[e.v]));
                }
            }
        }
    }
}