1753번: 최단 경로 (골드 4)

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

1753번: 최단경로

1. 문제 설명

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)

(2) 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.

(3) 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 

 

출력 조건

(1) 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다.

( 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다. )

 

입출력 예제

 

 

 

3. 풀이 및 코드

: 이 문제를 아래의 링크처럼 풀었더니 답은 제대로 나오지만 계속해서 메모리 초과가 나왔다.

다익스트라 (Dijkstra) (tistory.com)

 

( 원인을 찾아볼려고 했지만 정확하게 어떤 것이라고는 단정짓지 못했다. )

( 내 생각은 각 정점의 최단 거리를 구했는데도 계속해서 반복문이 돌아가서이다. )

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Node implements Comparable<Node>{
    int end, weight;
    
    Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
 
    // 우선순위 큐에서 최솟값으로 정렬
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
    
}
 
public class Main {
    static int V, E;
    static int K;
    static ArrayList<Node>[] list;
    static int[] dist;
    static boolean[] visited;
    
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    
    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(sc.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        K = Integer.parseInt(sc.readLine());
        
        list = new ArrayList[V+1];
        dist = new int[V+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        visited = new boolean[V+1];
        
        for(int i=1; i<=V; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i=1; i<=E; i++) {
            st = new StringTokenizer(sc.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));
        }
        solve(K);
        for(int i=1; i<=V; i++) {
            if(dist[i]==Integer.MAX_VALUE) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }
    
    static void solve(int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start, 0));
        dist[start] = 0;
        
        while(!q.isEmpty()) {
            Node curNode = q.poll();
            start = curNode.end;
            
            if(visited[start]) continue;
            visited[start] = true;
            
            for(Node node : list[start]) {
                if(dist[node.end] > dist[start]+node.weight) {
                    dist[node.end] = dist[start]+node.weight;
                    q.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }
}

( 우선순위 큐를 사용 시 사용하는 클래스(여기서는 Node)에서 Comparable의 인터페이스를 받아 compareTo() 를

구현하여 정렬해주는 기준을 세워야 한다. )