[Java] 백준 1238 : 파티

[문제]

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

1238번: 파티

 

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

 

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

 

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

 

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

[입력]

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

 

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

[출력]

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

[예제 입력]

[풀이 과정]

문제 요약 : N개의 마을에 각각의 한 명의 학생의 살고있다. X의 (1<= X <= N) 마을에서 파티를 하기로 했을 때 오고가는 비용이 가장 많은 학생의 비용을 출력하는 문제. 학생들이 게을러서 (?) 때문에 최단시간에 오고가야한다. 

 

풀이 : 문제를 보고 최단시간에 오고가야하는 비용을 구해야 하기때문에 다익스트라 알고리즘을 적용해야겠다고 생각했다. 시작점에서 다른 모든 정점까지의 최단비용을 구할 수 있으니 , 파티 끝나고(파티를 한 마을 : 시작점 )  각자의 마을(도착)로 돌아가는 비용을 구할 수 있다.

그럼 이제 각 마을에서 파티를 하는 마을로 가는 비용을 구하면 된다.  그래서 (자신의 마을 -> 파티한 마을)  + (파티한 마을->자신의 마을) 의 최대값을 구하면된다.

 

그런데 각 마을에서 파티를 하는 마을로 가는 비용은 어떻게 해야할까 ? 본인은 처음에 마을 개수만큼 반복문을 돌려 각 마을에서 다른 모든 마을로 가는 최소 비용을 구한다음 파티를 개최한 마을의 비용을 가져와서 정답을 구하려고 했다. 이렇게 되면 다익스트라를 마을 개수인 N번 만큼 돌려야 해서 비효율적이였다.

 

이렇게 접근 하지 않고 A 마을 -> B마을 의 단방향 관계를  따로 인접 리스트를 만들어 반대로 단방향 관계를 저장한다.  이 인접리스트를 가지고 파티를 개최한 마을 (시작점 ) -> 다른 모든 마을(도착점) 의 최소 비용을 구하면 각 마을에서 파티를 개최한 마을까지의 최소 비용을 한번에 구할 수 있다. 

훨씬 효율적으로 구할 수 있다.

 

정리하자면 

(1) 각 마을 ------> 파티 마을까지 가는 최소 비용 : 단방향관계를 반대로 저장한 인접리스트에서 시작지점을 X (파티 마을)로 해서 다익스트라 적용

(2) 파티마을 -----> 각 마을로 돌아가는 비용 : 입력값을 그대로 받은 인접리스트에서 시작지점을 X(파티 마을)로 해서 다익스트라 적용

 

따라서 , (1) , (2) 두 번의 다익스트라를 하면된다.

 

[수정 전 코드( 588ms) ]

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main1238 {

    static class Node {
        int idx ;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }

    static int N,M,X;
    static ArrayList<ArrayList<Node>> graph;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); //마을 개수
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken()); //파티하러갈 마을 번호

        //인접 리스트
          graph = new ArrayList<>();

        for(int i = 0; i <=N;i++){
            graph.add(new ArrayList<Node>());
        }

        //단방향 관계 연결
        for(int i = 0 ; i < M; i++){

            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            //단방향
            graph.get(from).add(new Node(to,cost));

        }

        //각 마을에 파티장으로 가는 비용
        int [] villageCost = new int[N+1];
        int []dist;
        for(int i = 1; i <=N;i++){
           dist = dijkstra(i,X);
           villageCost[i]=dist[X];
        }

        //파티장에서 집으로 가는 비용
        int [] homeCost = new int[N+1];
        homeCost =  dijkstra(X,-1);


        int maxCost = Integer.MIN_VALUE;

        for(int i =1; i<=N;i++){
            maxCost=Math.max(maxCost,villageCost[i]+homeCost[i]);
        }

        System.out.println(maxCost);

    }
    private static int[] dijkstra (int start ,int end){


        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.cost,o2.cost)));
        int [] dist = new int[N+1];

        for(int i =1; i<=N;i++){
            dist[i]= Integer.MAX_VALUE;
        }

        queue.add(new Node(start,0));
        dist[start]=0 ;;//출발지에서 출발지로 가는 비용은 0

        while (!queue.isEmpty()){

            Node currNode = queue.poll();

            if(currNode.idx==end){ //파티장에 왔다면 더 이상 탐색하지 않는다.
                break;
            }

            if(dist[currNode.idx] < currNode.cost ){
                continue;
            }

            for(int i = 0 ; i < graph.get(currNode.idx).size();i++){

                Node nxtNode = graph.get(currNode.idx).get(i);

                if(dist[nxtNode.idx] > dist[currNode.idx] + nxtNode.cost){
                    //최소 비용으로 갱신
                    dist[nxtNode.idx] = dist[currNode.idx] + nxtNode.cost;
                    queue.offer(new Node(nxtNode.idx,dist[nxtNode.idx]));
                }

            }

        }

        return dist;
    }
}

[수정 후 코드 (208ms)]

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main1238 {

    static class Node {
        int idx ;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }

    static int N,M,X;
    static ArrayList<ArrayList<Node>> graph;
    static ArrayList<ArrayList<Node>> reverseGraph;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); //마을 개수
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken()); //파티하러갈 마을 번호

        //인접 리스트
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        ArrayList<ArrayList<Node>> reverseGraph = new ArrayList<>();

        for(int i = 0; i <=N;i++){
            graph.add(new ArrayList<Node>());
            reverseGraph.add((new ArrayList<Node>()));
        }

        //단방향 관계 연결
        for(int i = 0 ; i < M; i++){

            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            //단방향
            graph.get(from).add(new Node(to,cost));
            //관계를 반대로 저장 ->  각마을에서 파티마을로 가는 최소 비용을 구하기 위함
            reverseGraph.get(to).add((new Node(from,cost)));

        }

        //각 마을에서 ->  파티장으로 가는  최소 비용
        int [] villageCost = dijkstra(X,reverseGraph);
        //파티를 개최한 마을 -> 각 마을 으로 가는 비용
        int [] homeCost =  dijkstra(X,graph);


        int maxCost = Integer.MIN_VALUE;

        for(int i =1; i<=N;i++){
            maxCost=Math.max(maxCost,villageCost[i]+homeCost[i]);
        }

        System.out.println(maxCost);

    }
    private static int[] dijkstra (int start ,ArrayList<ArrayList<Node>>graph){


        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.cost,o2.cost)));
        int [] dist = new int[N+1];

        for(int i =1; i<=N;i++){
            dist[i]= Integer.MAX_VALUE;
        }

        queue.add(new Node(start,0));
        dist[start]=0 ;;//출발지에서 출발지로 가는 비용은 0

        while (!queue.isEmpty()){

            Node currNode = queue.poll();


            if(dist[currNode.idx] < currNode.cost ){
                continue;
            }

            for(int i = 0 ; i < graph.get(currNode.idx).size();i++){

                Node nxtNode = graph.get(currNode.idx).get(i);

                if(dist[nxtNode.idx] > dist[currNode.idx] + nxtNode.cost){
                    //최소 비용으로 갱신
                    dist[nxtNode.idx] = dist[currNode.idx] + nxtNode.cost;
                    queue.offer(new Node(nxtNode.idx,dist[nxtNode.idx]));
                }

            }

        }

        return dist;
    }
}

[결과]

시간이나 메모리에서 많이 줄은걸 확인할 수 있다.