백준 1238번 파티 (JAVA)

백준 1238번 파티 (JAVA)

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

---

소스코드

- 단방향 도로 = 단방향 그래프

- 양방향 그래프(=무방향 그래프)는 백준 1504번 특정한 최단경로 문제 참고

백준 1504번 특정한 최단 경로 (JAVA)

- 왕복 거리 = 마을→파티장 + 파티장→마을

- 인접리스트 2개 구현 : 순방향 인접리스트, 역방향 인접리스트(파티장→마을 구할 때 사용)

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static int N, M, X, Ans; //N:학생 수(정점), M:도로(간선), X:파티장소
    private static int INF = Integer.MAX_VALUE;
    private static ArrayList<Node>[] adjList, reverseAdjList;
    private static class Node implements Comparable<Node>{
        int dest, cost;
        public Node(int dest, int cost){
            this.dest = dest;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node o){
            return this.cost - o.cost; //cost 기준 오름차순
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Ans = 0;

        adjList = new ArrayList[N+1]; //순방향 인접리스트
        reverseAdjList = new ArrayList[N+1]; //역방향 인접리스트

        //인접리스트 초기화
        for (int i = 0; i < N+1; i++) {
            adjList[i] = new ArrayList<>();
            reverseAdjList[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());

            adjList[start].add(new Node(end, time)); //순방향 인접리스트 셋팅
            reverseAdjList[end].add(new Node(start, time)); //역방향 인접리스트 셋팅
        }

        //시작점을 X로 잡고 adjList 기준으로 최단거리 구하면 각 마을 → X 까지 최단 거리 구할 수 있음
        //시작점을 X로 잡고 reverseAdjList 기준으로 최단거리 구하면 X → 각 마을 까지 최단 거리 구할 수 있음
        int[] cost = dijkstra(X, adjList); //마을 → X(파티장)까지 최단거리 배열
        int[] reverseCost = dijkstra(X, reverseAdjList); //X(파티장) → 각 마을까지 최단거리 배열

        for (int i = 1; i < N+1 ; i++) {
            Ans = Math.max(Ans, cost[i]+reverseCost[i]);
        }

        bw.write(Ans + "\n");
        bw.flush();
        bw.close();
        br.close();

    }
    private static int[] dijkstra(int start, ArrayList<Node>[] list){
        //최저비용 기준 탐색경로 저장 위한 우선순위 큐
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] tempCost = new int[N+1];
        boolean[] visited = new boolean[N+1];
        Arrays.fill(tempCost, INF); //거리(cost) 저장위한 배열 INF로 초기화
        Arrays.fill(visited, false); //방문여부 체크 배열 false로 초기화

        tempCost[start] = 0; //시작점이기 때문에 거리 0으로 셋팅
        pq.add(new Node(start, 0));

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

            if(visited[now.dest]) continue; //방문했던 정점이면 스킵
            visited[now.dest] = true; //미방문이면 방문으로(true)로 셋팅하고 for문 처리

            //간선 탐색
            for (Node next:list[now.dest]) {
                if(tempCost[next.dest] > next.cost + now.cost){
                    tempCost[next.dest] = next.cost + now.cost;
                    pq.add(new Node(next.dest, tempCost[next.dest]));
                }
            }
        }
        return tempCost;
    }

}