[다익스트라] 백준 1238번 파티 - JAVA

 

 

 

 

 

---

1. 출처

---

 

1238번: 파티

 

 

 

---

2. 설계

---

 

문제 이해

- N개의 섬이 있고, 각 섬에는 한 사람씩 살고 있다.

- 파티는 X번 섬에서 열린다. (X섬 중 1개)

- 각 친구들은 각자 사는 섬에서 파티 가는길 + 다시 집으로 오는 길 = 최단거리를 구하고 각 친구들의 왔다갔다 한 거리 중 가장 멀었던 곳을 선정하는 것이다.

 

 

1) 모든 섬을 다 안 거쳐도 된다.

2) 최단 거리를 구한다.

-> 프림이 아니고, 다익스트라를 쓰자!

 

 

설계

- 다익스트라는 알고리즘을 돌렸을 때 특정 시작 점에서 전체 노드로 가는 길의 최단 거리를 모두 구해준다.

- 때문에 우리는 먼저 파티 X 섬에서 각자의 집으로 돌아가는 길을 다익스트라로 돌려 모든 친구들의 집으로 돌아가는 최단 거리를 구해준다.

//도착지에서 출발지까지 오는 데 가장 최단 거리 저장
end_dist = new int[N+1];
for(int i=1;i<N+1;i++){
	end_dist[i]=Integer.MAX_VALUE;
}
end_dist[X] = 0;

end_dijstra(X);

 

- 그 뒤 각자의 집에서 파티를 가는 길의 최단 거리를 구해야 하기 때문에 START를 각자 집으로 N번 for문을 돌리며 다익스트라를 적용시킬 것이다.

//각 섬에서 X번 섬까지 오는 데 가장 오래 걸리는 시간은?
for(int start=1;start<=N;start++){
            
	start_dist = new int[N+1];
	for(int i=1;i<N+1;i++){
		start_dist[i]=Integer.MAX_VALUE;
	}

	start_dist[start] = 0;

	start_dijstra(start);
}

 

 

 

---

3. 전체 코드

---

import java.util.*;

public class Main {

    public static class Node implements Comparable<Node>{
        int num;
        int fee;
        public Node(int num, int fee){
            this.num=num;
            this.fee=fee;
        }

        @Override
        public int compareTo(Node o){
            return this.fee>o.fee?1:-1;
        }
    }

    static int N;
    static int M;
    static int X;
    static List<Node>[] adj;
    static int result;
    static int[] start_dist;
    static int[] end_dist;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M  = sc.nextInt();
        X = sc.nextInt();


        adj = new ArrayList[N+1];//1부터 시작
        for(int i=1;i<N+1;i++){
            adj[i]=new ArrayList<>();
        }

        for(int i=0;i<M;i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            int fee = sc.nextInt();
            adj[start].add(new Node(end, fee));
        }

        //입력 끝

        //도착지에서 출발지까지 오는 데 가장 최단 거리 저장
        end_dist = new int[N+1];
        for(int i=1;i<N+1;i++){
            end_dist[i]=Integer.MAX_VALUE;
        }
        end_dist[X] = 0;

        end_dijstra(X);

        //각 섬에서 X번 섬까지 오는 데 가장 오래 걸리는 시간은?
        for(int start=1;start<=N;start++){
            
            start_dist = new int[N+1];
            for(int i=1;i<N+1;i++){
                start_dist[i]=Integer.MAX_VALUE;
            }

            start_dist[start] = 0;

            start_dijstra(start);
        }

        System.out.println(result);

    }

    public static void start_dijstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean visited[] = new boolean[N+1];

        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(!visited[cur.num]){
                visited[cur.num] = true;

                for(int i=0;i<adj[cur.num].size();i++){
                    int next_num = adj[cur.num].get(i).num;
                    int next_fee = adj[cur.num].get(i).fee;

                    if(start_dist[next_num] > start_dist[cur.num]+next_fee){
                        start_dist[next_num] = start_dist[cur.num]+next_fee;
                        pq.add(new Node(next_num, start_dist[next_num]));
                    }
                }
            }
        }

        result = Math.max(end_dist[start]+start_dist[X], result);
    }


    public static void end_dijstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean visited[] = new boolean[N+1];

        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(!visited[cur.num]){
                visited[cur.num] = true;

                for(int i=0;i<adj[cur.num].size();i++){
                    int next_num = adj[cur.num].get(i).num;
                    int next_fee = adj[cur.num].get(i).fee;

                    if(end_dist[next_num] > end_dist[cur.num]+next_fee){
                        end_dist[next_num] = end_dist[cur.num]+next_fee;
                        pq.add(new Node(next_num, end_dist[next_num]));
                    }
                }
            }
        }

        result = Math.max(end_dist[X], result);
    }
}