[백준][Java] 1753번 최단경로 (다익스트라)

스스로 해결하지는 못하고 문제의 질문검색 탭을 뒤져서 반례등을 찾아서 해결함

 

메모리 초과 왜why??? 
모든 V를 전부 돌려서.. 그런듯 문제에서 주어진 edge만 탐색해야함
다익스트라 맨 처음 배울 때 for문 뺑뺑이 돌리는 식으로 짜면 틀리게됨

틀렸습니다 왜why??

반례 : 정점은 1개인데 edge가 없는 정점을 가리키는 경우
1 1
1
1 2 2

Line:44 부분에 간선을 체크할 때 존재하지 않는 정점을 체크하는 경우 continue해줌


또 틀렸습니다..

Line:32
visited[]를 확인할 필요가 없음.. 

 

다익스트라를

https://www.youtube.com/watch?v=QleeV_ipB7w&t=430s 

강의를 보고 공부를 했는데

기본적인 개념에 대해 설명해주는 코드라서 모든 1~V에서 1~V까지의 Dist를 탐색하기 때문에

시간, 메모리 초과함 이 때 필요한 개념이 visited라는 정점을 탐색했다는 개념을 추가해주는건데

visited가 없으면 정점을 계속 돌면서 못끝냄

 

Line:35에서 

List<int[]> list = curr.getEdgeList();

for(int i=0; i<list.size(); i++) { ... }

이걸로 교체해준 순간 visited는 필요 없는 개념이 되는 것 같음.. 어차피 존재하는 edge들만을 탐색해서

최소 거리를 갱신해주기 때문에.. 그냥 나중에 한번 더 풀어봐야할듯

 

210919

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int[] MinDist;
    static int INF = 10*300000*2;
    static List<Node> nodeList;
    
    static class Node{
        int num;
        List<int[]> edgeList = new ArrayList<>();
        
        public Node(int num) {
            this.num = num;
        }
    }
    
    static void Dijkstra(int K) {
        PriorityQueue<Node> pq = new PriorityQueue<>( (a,b) -> MinDist[a.num] - MinDist[b.num] );
        pq.offer(nodeList.get(K));
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.num;
            List<int[]> edgeList = curr.edgeList;
            
            for(int i=0; i<edgeList.size(); i++) {
                int v = edgeList.get(i)[0];
                int w = edgeList.get(i)[1];
                
                if(MinDist[v]> MinDist[u]+w) {
                    MinDist[v] = MinDist[u]+w;
                    pq.offer(nodeList.get(v));
                }
            }
            
        }
    }
    
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int V = stoi(str[0]);
        int E = stoi(str[1]);
        int K = stoi(br.readLine());
        
        MinDist = new int[V+1];
        Arrays.fill(MinDist, INF);
        nodeList = new ArrayList<>();
        for(int i=0; i<=V; i++) {
            nodeList.add(new Node(i));
        }
        
        for(int i=1; i<=E; i++) {
            str = br.readLine().split(" ");
            int u = stoi(str[0]);
            int v = stoi(str[1]);
            int w = stoi(str[2]);
            
            nodeList.get(u).edgeList.add(new int[] {v, w});
        }
        
        
        MinDist[K] = 0;
        Dijkstra(K);
        
        StringBuilder sBuilder = new StringBuilder();
        for (int i=1; i<MinDist.length; i++) {
            if(MinDist[i]==INF)
                sBuilder.append("INF\n");
            else
                sBuilder.append(MinDist[i]+"\n");
                
        }
        
        System.out.println(sBuilder.toString());
        
            
        
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
        
    
}

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static List<Node> NodeList;
    static final int INF = 300000*10*2;
    
    private static void dijkstra(int K) {
        PriorityQueue<Node> q = new PriorityQueue<>( (a,b)->a.getMinDist()-b.getMinDist()  );
        NodeList.get(K).setMinDist(0);
        q.offer(NodeList.get(K));
        
        while(!q.isEmpty()) {
            Node curr = q.poll();
            int u = curr.getNum();
            
            // 맨 처음 배운 강의에서 넣어줬던 코드
            // 이 visited라는 개념이 필요 없는 이유는...
            // visited를 해줘야 하는 경우가 for문 뺑뺑이인 경우임
            // for dist[i][j] 전부 돌리는 경우
            /*if(curr.isVisited()) continue;
            curr.setVisited(true);*/
            
            List<int[]> list = curr.getEdgeList();
            for(int i=0; i<list.size(); i++) {
                int v = list.get(i)[0];
                
                // 반례
                //  1 1
                //    1
                //    1 2 2
                //    answer : 0
                if(v>NodeList.size()-1) continue;
                
                int dist = list.get(i)[1];
                
                if(NodeList.get(v).getMinDist()
                        > NodeList.get(u).getMinDist()+dist) {
                    NodeList.get(v).setMinDist(NodeList.get(u).getMinDist()+dist);
                    q.offer(NodeList.get(v));
                }
            }
                
            
        }
        
        
    }
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int V = Integer.parseInt(str[0]);
        int E = Integer.parseInt(str[1]);
        
        int K = Integer.parseInt(br.readLine());
        
        
        NodeList = new ArrayList<>();
        
        for(int i=0; i<=V; i++) {
            NodeList.add(new Node(i));
        }
        
        for(int i=1; i<=E; i++) {
            str = br.readLine().split(" ");
            int u = Integer.parseInt(str[0]);
            int v = Integer.parseInt(str[1]);
            int w = Integer.parseInt(str[2]);
            
            NodeList.get(u).getEdgeList().add(new int[] {v,w});
        }
        
        dijkstra(K);
        
        for (int i=1; i<NodeList.size(); i++) {
            if(NodeList.get(i).getMinDist()==INF) 
                System.out.println("INF");
            else
                System.out.println(NodeList.get(i).getMinDist());
        }
 
        
//        bw.write("");
//        bw.flush(); 
//        bw.close();
    }
    
    public static class Node{
        private List<int[]> edgeList; //[{v1, Dist1}, {v2,Dist2},..]
        private int num;
        private boolean visited; // 의미 없는 variable
        private int minDist;
        
        Node(int num) {
            this.num = num;
            edgeList = new ArrayList<>();
            minDist=INF;
            visited=false;
        }
        
        
 
        public int getNum() {
            return num;
        }
 
 
 
        public void setNum(int num) {
            this.num = num;
        }
 
 
 
        public List<int[]> getEdgeList() {
            return edgeList;
        }
 
        public void setEdgeList(List<int[]> edgeList) {
            this.edgeList = edgeList;
        }
 
        public boolean isVisited() {
            return visited;
        }
 
        public void setVisited(boolean visited) {
            this.visited = visited;
        }
 
        public int getMinDist() {
            return minDist;
        }
 
        public void setMinDist(int minDist) {
            this.minDist = minDist;
        }
    }
}