백준_1753_최단경로 (다익스트라 알고리즘 (Dijkstra Algorithm))

한 정점에서 다른 정점으로 가는 최단 경로를 찾는 알고리즘

참고했던 블로그 (가장 잘 정리된 블로그)

 

1번 풀이(시간초과)

백준 1753번 최단경로를 통해 해당 알고리즘을 학습했다. 직관적으로 이해하기 위해 해당 방법으로 인접행렬을 사용하여 문제를 풀었기에 메모리 초과가 발생한다.

import java.util.Scanner;
 
public class boj_1753_최단경로 {
    static int[][] graph;
    static int V, E;
    static boolean[] visited;
    static int[] dist;
 
    public static void main(String[] args) {
 
        Scanner scanner = new Scanner(System.in);
 
        V = scanner.nextInt();
        E = scanner.nextInt();
        int startNode = scanner.nextInt();
        graph = new int[V + 1][V + 1];
        visited = new boolean[V + 1];
        dist = new int[V + 1];
        for (int i = 0; i < dist.length; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[startNode] = 0;
 
        visited[startNode] = true;
 
        for (int i = 0; i < E; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int value = scanner.nextInt();
 
            if (graph[start][end] == 0) {
                graph[start][end] = value;
            } else {
                graph[start][end] = Math.min(graph[start][end], value);
            }
        }
 
        /// Input ///
 
        djik(startNode);
 
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }
        }
    }
 
    public static void djik(int s) {
        int rowMin = Integer.MAX_VALUE;
        int minIdx = 0;
 
        for (int i = 1; i < graph.length; i++) {
            if (graph[s][i] != 0) {
                dist[i] = Math.min(graph[s][i] + dist[s], dist[i]);
            }
        }
        for (int i = 1; i < dist.length; i++) {
            if (rowMin > dist[i] && !visited[i]) {
                rowMin = dist[i];
                minIdx = i;
                visited[i] = true;
            }
        }
        if (minIdx != 0) {
            djik(minIdx);
        } else {
            return;
        }
    }
 
}

 

2번 풀이

해당 코드는 Queue와 ArrayList를 사용하여 푼 코드입니다.

 

"BUT" PriorityQueue를 사용하여 재귀를 돌지않고, 제일 짧은 경로만 PriorityQueue에 넣어주면, 시간을 확실히 줄일 수 있을 것 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class boj_1753_최단경로 {
    static int V, E;
    static int[] dist;
    static ArrayList<Edge>[] al;
    static boolean[] visited;
    static Queue<Edge> pq;
    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());
        dist = new int[V + 1];
        visited = new boolean[V + 1];
        al = new ArrayList[V + 1];
        int start = Integer.parseInt(br.readLine());
        for (int i = 0; i < V + 1; i++) {
            al[i] = new ArrayList<Edge>();
        }
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            al[x].add(new Edge(y, v));
        }
        for (int i = 0; i < al.length; i++) {
            ArrayList<Edge> a = al[i];
        }
        visited[start] = true;
        int INF = 987654321;
        Arrays.fill(dist, INF);
        pq = new LinkedList<>();
        dist[start] = 0;
        find(start);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == INF) {
                sb.append("INF").append("\n");
            } else {
                sb.append(dist[i]).append("\n");
            }
        }
        System.out.println(sb.toString());
        br.close();
    }
    public static void find(int s) {
        for (int j = 0; j < al[s].size(); j++) {
            pq.offer(new Edge(al[s].get(j).y, al[s].get(j).v));
        }
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            if (dist[e.y] > dist[s] + e.v) {
                dist[e.y] = dist[s] + e.v;
            }
        }
        int x = Integer.MAX_VALUE;
        int idx = -1;
        for (int i = 1; i < dist.length; i++) {
            if (!visited[i] && dist[i] != 0 && x > dist[i]) {
                x = Math.min(x, dist[i]);
                idx = i;
            }
        }
        if (idx != -1)
            visited[idx] = true;
        else
            return;
        find(idx);
    }
    public static class Edge {
        int y;
        int v;
        public Edge(int y, int v) {
            this.y = y;
            this.v = v;
        }
    }
}