[백준] 1753번 (java 자바)

내 처음 풀이 [틀림] => 메모리 초과 : 2차원 배열로 인한 듯 하다 

import java.util.*;

public class Main
{
    static final int INF = 3000000;
    static int MAX_N = 20001;
    static int V, E, K;
    static int[][] Graph;
    static int[] Dist = new int[MAX_N];
    
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt(); E = sc.nextInt(); K = sc.nextInt();
        Graph = new int[V + 1][V + 1];
        for(int i = 1; i < V; i++){
            for(int j = 1; j < V; j++){
                if(i == j) Graph[i][j] = 0;
                else Graph[i][j] = INF;
            }
        }
        for(int i = 0; i < E; i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            Graph[u][v] = w;
        }
        dijkstra(K);
        
        for(int i = 1; i < V + 1; i++){
            if(Dist[i] == INF){
                System.out.println("INF");
            }else System.out.println(Dist[i]);
        }
	}
	static void dijkstra(int src){
	    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);
	    boolean[] visited = new boolean[MAX_N];
	    for(int i = 1; i < V + 1; i++) Dist[i] = INF;
	    Dist[src] = 0;
	    pq.add(new int[] {0, src});
	    while(!pq.isEmpty()){
	        int[] curr = pq.poll();
	        int v = curr[1];
	        if(visited[v]) continue;
	        
	        visited[v] = true;
	        for(int i = 1; i < V; i++){
	            if(Dist[i] > Dist[v] + Graph[v][i]){
	                Dist[i] = Dist[v] + Graph[v][i];
	                pq.add(new int[] {Dist[i], i});
	            }
	        }
	        
	    }
	    
	}
}

 

다른 블로그 참조한 풀이

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

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

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

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

public class Main
{   
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 100_000_000;
    static int v,e,k;
    static List<Node>[] list;
    static int[] dist;
    
	public static void main(String[] args) throws IOException  {
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());
        list = new ArrayList[v + 1];
        dist = new int[v + 1];

        Arrays.fill(dist, INF);

        for(int i = 1; i <= v; i++){
            list[i] = new ArrayList<>();
        }
        // 리스트에 그래프 정보를 초기화
        for(int i = 0 ; i < e; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            // start에서 end로 가는 weight 가중치
            list[start].add(new Node(end, weight));
        }

        StringBuilder sb = new StringBuilder();
        dijkstra(k);
        // 출력 부분
        for(int i = 1; i <= v; i++){
            if(dist[i] == INF) sb.append("INF\n");
            else sb.append(dist[i] + "\n");
        }

        bw.write(sb.toString());
        bw.close();
        br.close();
    
	}
	
	private static void dijkstra(int start){
	    PriorityQueue<Node> queue = new PriorityQueue<>();
	    boolean[] check = new boolean[v+1];
	    queue.add(new Node(start, 0));
	    dist[start] = 0;
	    
	    while(!queue.isEmpty()){
	        Node currNode = queue.poll();
	        int curr = currNode.end;
	        
	        if(check[curr] == true) continue;
	        check[curr] = true;
	        
	        for(Node node : list[curr]){
	            if(dist[node.end] > dist[curr] + node.weight){
	                dist[node.end] = dist[curr] + node.weight;
	                queue.add(new Node(node.end, dist[node.end]));
	            }
	        }
	        
	        
	        
	    }
	    
	    
	}
}

 

 

==> 이차원 배열을 Array 코드로 바꿨더니 통과 됨

 

import java.util.*;

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

public class Main
{
    static final int INF = 987654321;
    static int MAX_N = 100000;
    static int V, E, K;
    static List<Node>[] Graph;
    static int[] Dist;
    
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt(); E = sc.nextInt(); K = sc.nextInt();
        
        Graph = new ArrayList[V + 1];
        Dist = new int[V + 1];
        
        Arrays.fill(Dist, INF);
        
        for(int i = 1; i < V + 1; i++){
            Graph[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < E; i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            Graph[u].add(new Node(v, w));
        }
        dijkstra(K);
        
        for(int i = 1; i < V + 1; i++){
            if(Dist[i] == INF){
                System.out.println("INF");
            }else System.out.println(Dist[i]);
        }
	}
	static void dijkstra(int src){
	    PriorityQueue<Node> pq = new PriorityQueue<>((a, b)->a.weight - b.weight);
	    boolean[] visited = new boolean[V + 1];
	    
	    Dist[src] = 0;
	    pq.add(new Node(src, 0));
	    while(!pq.isEmpty()){
	        Node curr = pq.poll();
	        int v = curr.end;
	        if(visited[v]) continue;
	        
	        visited[v] = true;
	        for(Node node : Graph[v]){
	            if(Dist[node.end] > Dist[v] + node.weight){
	                Dist[node.end] = Dist[v] + node.weight;
	                pq.add(new Node (node.end, Dist[node.end]));
	            }
	        }
	        
	    }
	    
	}
}