[백준] 1753번 : 최단경로 - Java

백준 1753: 최단경로 (Gold IIII)

---

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

출력

---

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

 

예제 입력

---

 

 

풀이

 

---

다익스트라 기본 문제 입니다.

예제입력에서 알 수 있듯이, 세 번째 줄부터 E번만큼 u(시작 정점), v(타겟 정점), w(가중치)가 주어집니다.

따로 Node클래스를 만들어준 후, 타겟 정점과, 가중치를 담을 수 있는 필드를 만들어줍니다.

여기서, 정점을 담을 수 있는 필드를 따로 만들어주지 않는 이유는, 이 Node들을 배열로 관리하여, 각각의 정점의 번호에 해당하는 index에 Node들을 ArrayList로 관리할 것이기때문입니다.

즉, List<Node>[] array로 이중배열의 형태로 Node들을 관리합니다.

array[1]은 1의 정점에서 타겟 정점에 대한 데이터가 담긴 Node들을 동적으로 할당받아 1번 정점이 어떤 타겟 정점(Node)들과 간선으로 연결이 되어있는지를 관리할 수 있게됩니다.

기본적인 문제의 풀이형태는 BFS입니다.

허나, 가중치를 도입하여야 하므로, 기존 queue로 구현하는 BFS에서 Priority queue를 사용하여 가중치를 토대로 값이 먼저 뽑혀나오도록 합니다.

distance 필드를 하나 놓고, 각각의 index를 target 정점이라고 생각하여 가중치의 합을 마스킹합니다.

각각의 distance 초기 설정값은, 임의의 큰 수를 놓습니다. 단, 20,000 * 10보다는 큰 수로 놓고, 정답을 도출할 때 각각의 distance를 탐색하여 값이 지정해둔 임의의 큰 수가 나올 경우 해당 정점은 순회를 하지못했다는 이야기가 되므로 "INF"을 출력하도록 합니다.

 

아래는 정답 코드입니다.

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

class Node implements Comparable<Node>{
    int target, weight;

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

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

class Main{

    public static List<Node>[] list;
    public static boolean[] isVisited;
    public static int[] distance;
    private static int INF = 100000000;


    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()), E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        isVisited = new boolean[V+1];
        list = new ArrayList[V+1];
        distance = new int[V+1];

        Arrays.fill(distance, INF);

        for (int i = 1; i < V+1; i++) {
            list[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());
            list[u].add(new Node(v, w));
        }
        StringBuilder sb = new StringBuilder();

        dijkstra(K);

        for (int i = 1; i < V+1; i++) {
            if(distance[i] == INF) {
                sb.append("INF\n");
            }else{
                sb.append(distance[i] + "\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

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

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            int next = cur.target;

            if(!isVisited[next]){
                isVisited[next] = true;

                for(Node node : list[next]){
                    if(distance[node.target] > distance[next] + node.weight){
                        distance[node.target] = distance[next] + node.weight;
                        pq.add(new Node(node.target, distance[node.target]));
                    }
                }
            }
        }

    }
}