[백준] 1735번 : 최단경로 (java)

1753번: 최단경로 (acmicpc.net)

1753번: 최단경로

어떻게 생각하고 문제를 풀었는가?

주어지는 것은 방향성이 있는 그래프이고 구해야 하는 것은 모든 정점으로의 최단 경로입니다.

시작 정점에서부터 시작하여 연결된 경로의 정점에 가중치를 갱신하는 다익스트라 알고리즘을 사용하고자 하였습니다.

코드

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

class Main {
    static int V, E, K, INF;
    static List<Node>[] nodeList;
    static boolean[] visited;
    static int[] result;
    static PriorityQueue<Node> queue = new PriorityQueue<>((a,b) -> a.value-b.value);
    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());
        INF = V*11;
        nodeList = new ArrayList[V+1];
        for(int i=1; i<=V; i++){
            nodeList[i] = new ArrayList<>();
        }
        visited = new boolean[V+1];
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            nodeList[Integer.parseInt(st.nextToken())].add(new Node(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
        }
        result = new int[V+1];
        Arrays.fill(result,INF);
        result[K] = 0;
        queue.offer(new Node(K,result[K]));
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(visited[cur.dest]) continue;
            visited[cur.dest] = true;
            for(Node next : nodeList[cur.dest] ){
                int dest = next.dest;
                if(!visited[dest]&&result[dest]>cur.value+next.value){
                    result[dest] = cur.value+next.value;
                    queue.offer(new Node(dest,result[dest]));
                }
            }
        }
        for(int i=1; i<=V; i++){
            System.out.println(result[i]==INF? "INF" : result[i]);
        }
        br.close();
    }

    public static class Node{
        private int dest;
        private int value;
        public Node(int dest,int value){
            this.dest = dest;
            this.value = value;
        }
    }
}

PriorityQueue를 사용하여 최단 경로를 더 빨리 구할 수 있도록 코드를 작성하였습니다.

문제를 풀 때 주의해야 할 점은 가중치를 저장할 때 2차원 배열로 선언하지 않는 것입니다.

주어지는 정점의 개수는 최대 20,000개 이므로 2차원 배열로 방향성을 나타내고자 한다면 20,000 x 20,000의 메모리 공간을 사용해야 합니다.

List와 같은 컬렉션을 사용하여 가중치를 저장해야 메모리 초과가 발생하지 않습니다.