[백준] 1238번: 파티 (Java)

1. 문제설명

N개의 마을에 각각 한 명의 학생이 있다. 이 마을 사이에는 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들을 최단 시간에 파티(X)에 오고 가기를 원한다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생을 구하는 문제이다.

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

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• 인접리스트 형식으로 그래프 정보를 입력받는다.
  • 정방향 그래프: X 마을에서 각 마을로 가는 경로를 구할 때 사용
  • 역방향 그래프: 각 마을에서 X 마을로 가는 경로를 구할 때 사용
• 다익스트라 알고리즘을 두 번 실행한다.
  • 첫 번째: 정방향 그래프를 사용하여 X에서 각 마을로 가는 최단 경로를 구함
  • 두 번째: 역방향 그래프를 사용하여 각 마을에서 X로 가는 최단 경로를 구함
• 두 최단 경로를 더해 왕복 시간을 계산하고, 최댓값을 출력한다.

 

3. 최종 코드

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

public class Main {
    static int n, m; // 마을 수, 간선 수
    static int x; // 파티가 열리는 마을
    static List<Node>[] list, reverseList; // 정방향 및 역방향 인접 리스트
    static long[] distToX, distFromX; // X로 가는 거리와 X에서 오는 거리
    static final long INF = Long.MAX_VALUE; // 무한대 값

    static class Node implements Comparable<Node> {
        int vertex; // 도착 마을
        long time; // 걸리는 시간

        public Node(int vertex, long time) { // 생성자
            this.vertex = vertex;
            this.time = time;
        }

        @Override
        public int compareTo(Node o) {
            // 시간 짧은 순으로 정렬
            if(time > o.time) return 1;
            else return -1;
        }
    }

    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());

        // 정방향 및 역방향 인접리스트 초기화
        list = new List[n+1];
        reverseList = new List[n+1];
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
            reverseList[i] = new ArrayList<>();
        }

        distToX = new long[n+1];
        distFromX = new long[n+1];
        Arrays.fill(distToX, INF);
        Arrays.fill(distFromX, INF);

        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());
            list[start].add(new Node(end, time)); // 정방향
            reverseList[end].add(new Node(start, time)); // 역방향
        }

        // 1. X에서 각 마을로 가는 최단 거리 구하기 (정방향 리스트 사용)
        dijkstra(list, distFromX, x);

        // 2. 각 마을에서 X로 가는 최단 거리 구하기 (역방향 리스트 사용)
        dijkstra(reverseList, distToX, x);

        // 각 마을에서 왕복 시간 계산 후 최댓값 구하기
        long max = 0L;
        for(int i=1; i<=n; i++) {
            long sum = distToX[i] + distFromX[i]; // 왕복 시간
            if(sum > max) max = sum; // 최댓값 갱신
        }
        System.out.println(max);
    }

    // 다익스트라 알고리즘
    public static void dijkstra(List<Node>[] graph, long[] dist, int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        dist[start] = 0; // 출발지의 최단 거리는 0으로 설정
        q.offer(new Node(start, 0));

        while (!q.isEmpty()) {
            Node current = q.poll();

            if (dist[current.vertex] < current.time) continue; // 이미 처리된 노드이면 무시

            // 현재 노드와 연결된 다른 인접 노드 확인
            for (Node next : graph[current.vertex]) {
                if (dist[next.vertex] > dist[current.vertex] + next.time) {
                    dist[next.vertex] = dist[current.vertex] + next.time;
                    q.offer(new Node(next.vertex, dist[next.vertex]));
                }
            }
        }
    }
}