[백준 1753] 최단경로(JAVA)

백준 1753번 문제 - 최단경로

1753번: 최단경로

---

문제 분석 

 

 

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

---

해결 포인트

 

• 다익스트라(Dijkstra) 알고리즘 사용
• Edge 클래스 구현
  • 도착지 v
  • 가중치 w
• 결과를 저장할 results 배열 구현
• Edge Comparable는 가중치가 작은 순으로 정렬되도록 구현
• 우선순위 큐 사용
  •  Queue<Edge> q = new PriorityQueue<>(); 
• 방문 확인 visited 배열 구현
• 처음 시작 위치 큐에 삽입 
  •  q.add(new Edge(start, 0)); 
• 큐가 빌 때까지 반복
  
  • 큐에서 하나 꺼내기
  • 방문한 위치면 패스(continue)
  • 방문 안한 위치면 방문 등록 후, 갈 수 있는 공간 큐에 추가
    results[e.v] = Math.min(results[e.v], e.w + edge.w);
    queue.add(new Edge(e.v, e.w + edge.w));

---

코드

 

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

public class Main {
    public static int [] results;
    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());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        ArrayList<Edge> [] edges = new ArrayList[V+1];
        for (int i = 1; i <= V; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; 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());

            edges[u].add(new Edge(v,w));
        }

        results = new int[V+1];
        Arrays.fill(results, Integer.MAX_VALUE);

        Dijkstra(V, K, edges);

        for (int i = 1; i <= V; i++) {
            if(results[i] == Integer.MAX_VALUE)
                bw.write("INF\n");
            else
                bw.write(results[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void Dijkstra(int V, int start, ArrayList<Edge> [] edges) {
        Queue<Edge> queue = new PriorityQueue<>();
        boolean [] visited = new boolean[V+1];

        queue.add(new Edge(start, 0));
        results[start] = 0;

        while (!queue.isEmpty()) {
            Edge edge = queue.poll();

            if (!visited[edge.v]) {
                visited[edge.v] = true;
                for (Edge e : edges[edge.v]) {
                    results[e.v] = Math.min(results[e.v], e.w + edge.w);
                    queue.add(new Edge(e.v, e.w + edge.w));
                }
            }
        }
    }

    public static class Edge implements Comparable<Edge> {
        int v;
        int w;
        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            if(w == o.w) {
                return v - o.v;
            }
            return w - o.w;
        }
    }
}