[백준 1238] 파티 (Java) - 다익스트라

https://www.acmicpc.net/problem/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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1 복사

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1 복사

10

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N,M,X;
    static ArrayList<Road>[] roads;
    static int[] depart;
    static int[] timeTaken;
    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()); // 파티 장소

        roads = new ArrayList[N+1]; // 도로 번호 1부터 시작
        depart = new int[N+1]; // 집 -> 파티장소 (출발소요시간)

        // 도로 인접노드리스트 초기화
        for(int i=1; i<N+1; i++){
            roads[i] = new ArrayList<>();
        }

        // 도로정보 입력받기
        for (int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()); // 시작점
            int end = Integer.parseInt(st.nextToken()); // 도착점
            int time = Integer.parseInt(st.nextToken()); // 소요시간

            // 단방향 도로
            roads[start].add(new Road(end, time));
        }

        // 집 -> 파티장소(X) 최단 소요시간
        for(int i=1; i<N+1; i++){
            timeTaken = new int[N+1]; // 소요시간 배열 초기화
            Arrays.fill(timeTaken, Integer.MAX_VALUE);

            timeTaken[i] = 0; // 출발노드 소요시간 0으로 초기화
            dijkstra(i); // 다익스트라 수행

            // i출발 -> 파티장소 최단 소요시간 기록
            depart[i] = timeTaken[X];
        }

        // 파티장소(X) -> 집 최단 소요시간
        timeTaken = new int[N+1]; // 소요시간 배열 초기화
        Arrays.fill(timeTaken, Integer.MAX_VALUE);
        timeTaken[X] = 0; // 출발노드 소요시간 0으로 초기화
        dijkstra(X); // 파티장소(X) 출발 다익스트라 수행

        int max = Integer.MIN_VALUE;
        for(int i=1; i<N+1; i++){
            max = Math.max(max, timeTaken[i] + depart[i]);
        }

        System.out.println(max);
    }
    private static void dijkstra(int start){
        PriorityQueue<Road> pq = new PriorityQueue<>();
        pq.offer(new Road(start, 0));

        while (!pq.isEmpty()){
            Road now = pq.poll();

            // 현재 노드의 최단경로가 이미 더 짧다면 무시
            if (now.time > timeTaken[now.num]) continue;

            for(Road next : roads[now.num]){
                int newTimeTaken = timeTaken[now.num] + next.time; // 새로운 경로 소요시간
                if (newTimeTaken < timeTaken[next.num]){
                    timeTaken[next.num] = newTimeTaken; // 새로운경로 소요시간으로 update
                    pq.add(new Road(next.num, newTimeTaken));
                }
            }
        }
    }
}
class Road implements Comparable<Road>{
    int num; // 도로 도착도시 번호
    int time; // 소요시간

    public Road(int des, int time){
        this.num = des;
        this.time = time;
    }

    @Override
    public int compareTo(Road o) {
        return this.time - o.time; // 소요시간 오름차순
    }
}

• 다익스트라를 활용한 문제
• [(집 -> 파티장소) 최단거리 + (파티장소 -> 집) 최단거리]의 최댓값을 구하는 문제
• 단방향 그래프이기 때문에 집-> 파티장소, 파티장소 -> 집 가는 경로가 서로 다를 수 있다.
• N(학생수), 도로수(M), 파티장소 도시번호(X)를 받는다.
• Road: 도로정보에는 도착점 도시정보, 소요시간이 있으므로 이것들을 모두 저장할 클래스를 새로 정의하여 선언한다.
  • 최소 소요시간을 구하고자 하는 것이므로 time을 오름차순으로 정렬할 수 있도록 Comparable을 implement해줬다.
• roads : 단방향 도로이므로 단방향으로 그래프 정보값을 입력해준다.

집 -> 파티장소(X) 최단소요시간 구하기

// 집 -> 파티장소(X) 최단 소요시간
        for(int i=1; i<N+1; i++){
            timeTaken = new int[N+1]; // 소요시간 배열 초기화
            Arrays.fill(timeTaken, Integer.MAX_VALUE);

            timeTaken[i] = 0; // 출발노드 소요시간 0으로 초기화
            dijkstra(i); // 다익스트라 수행

            // i출발 -> 파티장소 최단 소요시간 기록
            depart[i] = timeTaken[X];
        }

• 집 -> 파티장소로 가는 최소 소요시간을 구할때는 출발노드가 각자 다르다
• 최단소요시간을 담을 timeTaken을 초기화해주고, MAX_VALUE로 채워준다.
• 그리고 출발노드만 소요시간 0으로 초기화해주고 다익스트라 수행한다.
• 다익스트라를 모두 수행하면, timeTaken에는 집 -> 다른 모든 노드로까지의 최소 소요시간이 기록됐을 것이다.
• 궁금한 것은 X까지의 최소소요시간이므로 timeTaken[x]값을 depart[i]에 저장해준다.

파티장소(X) -> 집 최단소요시간

// 파티장소(X) -> 집 최단 소요시간
        timeTaken = new int[N+1]; // 소요시간 배열 초기화
        Arrays.fill(timeTaken, Integer.MAX_VALUE);
        timeTaken[X] = 0; // 출발노드 소요시간 0으로 초기화
        dijkstra(X); // 파티장소(X) 출발 다익스트라 수행

• 파티장소에서 집으로 가는 최단소요시간은 출발노드가 모두 동일하다.
• 즉, 다익스트라를 한번만 수행해주면된다.
• 다시 timeTaken 배열 초기화, MAX_VALUE로 채워준 후 출발노드만 소요시간을 0으로 초기화해준다.
• 파티장소X 노드부터 다익스트라를 수행해주면된다.

(집-> 파티장소) 최단소요시간 + (파티장소 -> 집) 최단소요시간의 최댓값 구하기

int max = Integer.MIN_VALUE;
        for(int i=1; i<N+1; i++){
            max = Math.max(max, timeTaken[i] + depart[i]);
        }

• 각 (집 -> 파티장소)로 이동하는데 소요된 최소소요시간 값과 timeTaken(파티장소 -> 집)값을 더해서 max값과 최대값 비교한다.
• 최종 max값을 출력하면 됨