백준(BOJ) 1753: 최단경로

https://www.acmicpc.net/problem/1753

처음에 인접리스트로 풀었다. 통과가 되었다. 하지만 방향그래프인만큼 인접행렬로 풀려고 시도를 하였다 => 메모리 초과가 났고 아래 글을 발견했다.  관련내용은 "3."번이다. https://www.acmicpc.net/board/view/34516

 

따라서, 방향그래프라고 해서 반드시 인접행렬을 사용해야만 하는 것은아니다. 아래는 인접행렬로 구현한 메모리초과가 나는 풀이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Testing3 {

    static class Point {
        int vertex;
        int weight;

        Point(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        int getWeight() {
            return weight;
        }

        int getVertex() {
            return vertex;
        }

    }

    static final int INF = 987654321;

    public static void solution(int[][] graph, int start) {
        int size = graph.length;
        boolean[] visited = new boolean[size];
        int[] dist = new int[size];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(Point::getWeight));
        pq.add(new Point(start, 0));
        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (!visited[cur.vertex]) {
                visited[cur.vertex] = true;
                for(int i=1;i<size;i++){
                    if(graph[cur.vertex][i]!=INF && !visited[i]){
                        if(dist[cur.vertex]+graph[cur.vertex][i]<dist[i]){
                            dist[i]=dist[cur.vertex]+graph[cur.vertex][i];
                            pq.add(new Point(i, dist[i]));
                        }
                    }
                }
            }
        }

        for (int i = 1; i < size; i++) {
            if (dist[i] != INF)
                System.out.println(dist[i]);
            else
                System.out.println("INF");
        }

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(br.readLine());
        int[][] graph = new int[n + 1][n + 1];
        for(int i=0;i<n+1;i++){
            Arrays.fill(graph[i],INF);
        }
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int begin = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            graph[begin][end] = weight;
        }
        solution(graph, start);

    }
}

 

아래는 인접리스트를 이용한 정답코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PipedInputStream;
import java.util.*;

public class Main {
    static final int INF = 987654321;

    static class Point {
        int v;
        int weight;

        Point(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }

        int getWeight() {
            return weight;
        }
    }

    public static void solution(List<List<Point>> graph, int start) {
        int size = graph.size();
        boolean[] visited = new boolean[size];
        int[] dist = new int[size];
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(Point::getWeight));
        Arrays.fill(dist, INF);
        dist[start] = 0;
        pq.add(new Point(start, 0));

        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (!visited[cur.v]) {
                visited[cur.v] = true;

                for (var nextV : graph.get(cur.v)) {
                    if (dist[cur.v] + nextV.getWeight() < dist[nextV.v]) {
                        dist[nextV.v] = dist[cur.v] + nextV.getWeight();
                        pq.add(new Point(nextV.v, dist[nextV.v]));
                    }
                }
            }
        }
        for (int i = 1; i < size; i++) {
            if (dist[i] != INF)
                System.out.println(dist[i]);
            else
                System.out.println("INF");
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(br.readLine());
        List<List<Point>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i < n + 1; i++)
            graph.add(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());
            graph.get(u).add(new Point(v, w));
        }
        solution(graph, start);

    }
}