[JAVA] 파티 1238

 

문제는 각 지점에서 X까지의 최단거리 + X에서 각 지점까지의 최단거리이다. 

최단거리 문제를 해결하기 위해서 다익스트라, 벨만, 플로이드 워셜을 고려해볼 수 있는데

일단 음수 사이클이 존재하지 않으므로 다익스트라와, 플로이드 워셜을 고민해보았고,

 

처음에는 모든 정점에서의 거리가 필요할 것 같아서 플로이드 워셜인가 싶었지만,

플로이드워셜의 시간복잡도 O(V^3) 1000^3 이라 10억 불가..

다익스트라로 해결할 경우 V(logV)E 100 * 8 * 10000 800만 -> 시간복잡도상 더 빠를 것 같고 다익스트라가 손에 더 익숙하기 떄문에 다익스트라로 결정

 

문제로 넘어와서 dist[][]를 만들고 각점들마다 최단거리를 다 구하고 dist[i][x] + dist[x][i]의 최대값을 구하면 끝나는 문제

 

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

class Main {
    

    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int x = Integer.parseInt(input[2]);
        
        int[][] dist = new int [n+1][n+1];
        
        
        ArrayList<ArrayList<Edge>> edges = new ArrayList<>();
        edges.add(new ArrayList<>());
        for(int i =1; i<=n; i++){
            int[] t = new int[n+1];    
            Arrays.fill(t, Integer.MAX_VALUE-101);
            dist[i] = t;
            
            edges.add(new ArrayList<>());
        }
        
        
        
        
        for(int i=0; i<m; i++){
            input = br.readLine().split(" ");
            edges.get(Integer.parseInt(input[0])).add(new Edge(Integer.parseInt(input[1]), Integer.parseInt(input[2])));
        }
        
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.w-o2.w);
        
        for(int i =1; i<=n; i++){
            int start = i;
            dist[start][start] = 0;
            
            pq.offer(new Edge(start, 0));
            
            while(!pq.isEmpty()){
                Edge e = pq.poll();
                int here = e.to;
                int w = e.w;
                
                
                if(w > dist[start][here]) continue;
                
                for(Edge ne: edges.get(here)){
                    int nw = w + ne.w;
                    int to = ne.to;
                    if(dist[start][to] > nw){
                        dist[start][to] = nw;
                        pq.offer(new Edge(to, nw));
                    }
                }
            }
        }
        int answer= -1;
        
        for(int i =1; i<=n; i++){
            answer = Math.max(answer, dist[i][x] + dist[x][i]);
        }
        
        bw.write(answer+ "");
        
        bw.flush();
        bw.close();
        br.close();
    }
    
        static class Edge{
        int to;
        int w;
        
        Edge(int to, int w){
            this.to = to;
            this.w =w;
        }
        
    }
}

 

 

다풀고나서 다른 사람해설을 보다 정말 와우한 해설을 보았다....

X로부터 다른 노드들까지의 거리는 주어진 간선을 통해서 쉽게 구할 수 있지만

다른 노드들로부터 X까지의 거리를 구하기 위해선 모든 정점에 대해서 다익스트라를 돌았어야했다.

 

하지만 모든 간선들을 꺼꾸로 배치하고 X에서 다익스트라를 돌리면 각 정점에서부터 X까지의 거리가 나온다. 
직관적인거 같으면서도 그림을 그려보면 납득이 된다..

이렇게 푼다면 시간복잡도가 2*ELog(v) 므로 무려 n/2배나 빨라졌다 WOW  

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

class Main {
    

    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int x = Integer.parseInt(input[2]);
        
        int[] distFromX = new int[n+1];
        int[] distToX = new int[n+1];
        Arrays.fill(distFromX, Integer.MAX_VALUE-101);
        Arrays.fill(distToX, Integer.MAX_VALUE-101);
        ArrayList<ArrayList<Edge>> edges = new ArrayList<>();
        ArrayList<ArrayList<Edge>> reverse = new ArrayList<>();

        for(int i =0; i<=n; i++){
            edges.add(new ArrayList<>());
            reverse.add(new ArrayList<>());
        }
        
        
        
        
        for(int i=0; i<m; i++){
            input = br.readLine().split(" ");
            edges.get(Integer.parseInt(input[0])).add(new Edge(Integer.parseInt(input[1]), Integer.parseInt(input[2])));
            reverse.get(Integer.parseInt(input[1])).add(new Edge(Integer.parseInt(input[0]), Integer.parseInt(input[2])));
        }
        
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.w-o2.w);
        
        
            
            distFromX[x] = 0;
            
            pq.offer(new Edge(x, 0));
            
            while(!pq.isEmpty()){
                Edge e = pq.poll();
                int here = e.to;
                int w = e.w;
                
                
                if(w > distFromX[here]) continue;
                
                for(Edge ne: edges.get(here)){
                    int nw = w + ne.w;
                    int to = ne.to;
                    if(distFromX[to] > nw){
                        distFromX[to] = nw;
                        pq.offer(new Edge(to, nw));
                    }
                }
            }
            
            distToX[x] = 0;
            
            pq.offer(new Edge(x, 0));
            
            while(!pq.isEmpty()){
                Edge e = pq.poll();
                int here = e.to;
                int w = e.w;
                
                
                if(w > distToX[here]) continue;
                
                for(Edge ne: reverse.get(here)){
                    int nw = w + ne.w;
                    int to = ne.to;
                    if(distToX[to] > nw){
                        distToX[to] = nw;
                        pq.offer(new Edge(to, nw));
                    }
                }
            }
        
        int answer= -1;
        
        for(int i =1; i<=n; i++){
            answer = Math.max(answer, distFromX[i] + distToX[i]);
        }
        
        bw.write(answer+ "");
        
        bw.flush();
        bw.close();
        br.close();
    }
    
        static class Edge{
        int to;
        int w;
        
        Edge(int to, int w){
            this.to = to;
            this.w =w;
        }
        
    }
}

 

출처: https://www.acmicpc.net/problem/1238

수정후 시간복잡도와 메모리 사용률이 훨씬 급감했음을 알 수 있다.