[BOJ] 1238 파티 - Java

✨ 그래프 👉 다익스트라 (최단경로 탐색 알고리즘)

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

1238번: 파티

---

📍 고려해야할 점 

• 각 학생들의 집에서 파티 장소까지 오고 가는 데 걸리는 최단 시간 구하기
• 도로들은 단방향 👉 길마다 걸리는 시간이 다르므로 오고 가는 길 또한 다름 !
• N명의 학생들 중 오고 가는 데 가장 많은 시간을 소비한 학생 출력

 

 

🕹️ 풀이과정 

집에서 파티 장소까지 가는 데 걸리는 최단 시간 + 파티 장소에서 집까지 가는 데 걸리는 최단 시간을 구해 이 중 가장 많은 시간을 소비한 학생을 구하면 된다. 

 

학생의 시작점, 끝점, 걸린 시간이 입력 데이터로 주어지므로 파티 장소에서 집까지 가는 데 걸리는 시간은 하나의 정점에서 다른 모든 정점까지의 최단 시간을 구하는 다익스트라 알고리즘을 사용하면 된다. 

 

그러나, 학생의 집에서 파티장소까지 가는 데 걸린 시간을 구하려면 각 학생마다 다익스트라 알고리즘을 사용해서 구해야 한다. 

입력 데이터로 주어진 값을 역방향으로 저장하면 모든 학생마다 다익스트라 알고리즘을 사용하지 않고, 한 번의 다익스트라를 통해 구할 수 있다. 

역방향으로 저장한 그래프

☀️ 역뱡향으로 저장 : 집에서 파티까지 가는 데 걸리는 시간을 파티에서 집까지 가는 데 걸리는 시간으로 저장하는 것 !

 

 

 

 

 

 

👩‍💻 전체 코드 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class BOJ_1238_파티{
    static int N, M, X;
    static ArrayList<Info>[] homeToParty;
    static ArrayList<Info>[] partyToHome;
    static int[] pthDist;
    static int[] htpDist;

    static class Info implements Comparable<Info>{
        int v, w;

        public Info(int v, int w){
            this.v=v;
            this.w=w;
        }
        @Override
        public int compareTo(Info o){
            return w-o.w;
        }
    }

    static void dijkstra(ArrayList<Info>[] arrList, int[] dist){
        PriorityQueue<Info> pq = new PriorityQueue<>();
        pq.add(new Info(X, 0));

        dist[X]=0;
        while(!pq.isEmpty()){
            Info now = pq.poll();

            for (Info next : arrList[now.v]) {
                if(dist[next.v] > dist[now.v]+next.w){
                    dist[next.v] = dist[now.v]+next.w;
                    pq.add(new Info(next.v, dist[next.v]));
                }
            }
        }
    }

    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 = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        homeToParty = new ArrayList[N+1]; // 집에서 파티 장소로 가는 데 소요되는 최단 시간
        partyToHome = new ArrayList[N+1]; // 파티 장소에서 집으로 돌아가는 데 소요되는 최단 시간

        for(int i=1; i<=N; i++){
            homeToParty[i] = new ArrayList<>();
            partyToHome[i] = new ArrayList<>();
        }

        pthDist = new int[N+1];
        htpDist = new int[N+1];

        Arrays.fill(pthDist, Integer.MAX_VALUE);
        Arrays.fill(htpDist, Integer.MAX_VALUE);

        for(int i=1; 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());

            partyToHome[start].add(new Info(end, time));
            homeToParty[end].add(new Info(start, time));
        }

        dijkstra(partyToHome, pthDist);
        dijkstra(homeToParty, htpDist);

        int ans=-1;
        for(int i=1; i<=N; i++){
            ans = Math.max(pthDist[i] + htpDist[i], ans);
        }

        bw.write(ans + " ");
        bw.flush();
        bw.close();
    }
}