[백준 1238] 파티

문제

접근

• 가중치 O
• 방향 O
  방향과 가중치가 있는 그래프이기 때문에 클래스를 활용한 인접리스트를 구현하였다.

그 후에 모든 학생이 위치한 노드로부터 X(파티 장소) 까지로의 최단 거리와 X(파티 장소) 에서 다시 자신이 위치한 마을로 돌아가는 최단 거리를 합친 것 중 가장 큰 값을 출력해야 하기 때문에 다익스트라 알고리즘을 사용하였다.

다익스트라 알고리즘은 그래프에서 하나의 시작 노드로부터 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 동작하며, 음의 가중치가 없는 그래프에 적합합니다.

다익스트라 알고리즘은 음의 가중치를 가진 그래프에서 사용할 수 없습니다. 음의 가중치가 있는 경우, 벨만-포드 알고리즘과 같은 다른 알고리즘을 사용해야 합니다.

문제 풀이

1. 가중치 있는 인접 리스트 구현
   • 이때, Node클래스에서 Comparable 인터페이스를 구현하고, compareTo 메서드를 오버라이딩하여 가중치(w)를 기준으로 오름차순 정렬을 하도록 변경했습니다. 이를 통해 우선순위 큐에서 올바르게 동작하도록 했습니다.
2. 다익스트라 메서드 구현
3. 각 노드에서 다른 노드까지의 최단 경로를 계산
   • distFromX : 파티 장소 X에서 다른 모드 노드까지의 최단 경로를 계산
   • 각 노드 i에서 X까지의 최단 경로를 계산한 후, 이 값과 disFromX[i]를 더해
   • 파티에 갔다가 돌아오는 총 시간을 계산한다.
   • 최대 시간 계산 : 모든 노드에서 파티를 갔다가 돌아오는 시간 중 최대 시간을 maxTime 에 저장하고 이를 출력한다.

시간 복잡도

O((V + E) log V)

전체 코드

package baekjoon_day01;
import java.io.*;
import java.util.*;

public class Party_1238 {
    static class Node implements Comparable<Node> {
        int v;
        int w;

        Node(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node other) {
            // 짧은 거리 선택.
            return Integer.compare(this.w, other.w);
            /*
            Integer.compare 메서드는 두 정수를 비교하여 다음 값을 반환합니다:
                음수 값: this.w가 other.w보다 작은 경우.
                0: this.w와 other.w가 같은 경우.
                양수 값: this.w가 other.w보다 큰 경우.
             */
        }
    }
    static int N, M, X;
    static List<Node>[] adj;
    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());

        adj = new List[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            int nxt = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            adj[cur].add(new Node(nxt, weight));
        }

        int[] distFromX = dijkstra(X); // X로부터 모든 노드까지의 최단 거리 배열

        int maxTime = 0;
        for (int i = 1; i <= N; i++) {
            if (i == X) continue;
            int[] distToX = dijkstra(i); // 다른 노드에서부터 X 노드까지의 최단 거리.
            int totalTime = distToX[X] + distFromX[i]; // i~X 로 가는 최단 거리 + X~i 로 가는 최단 거리
            maxTime = Math.max(maxTime, totalTime);
        }
        System.out.println(maxTime);

    }

    private static int[] dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        int[] dist = new int[N + 1]; // 각 노드에 대한 최단 거리 저장하는 배열 초기화
        Arrays.fill(dist, Integer.MAX_VALUE); // 모든 노드까지의 거리를 무한대로 설정
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node curNode = pq.poll(); // 우선순위 큐에서 가장 작은 가중치를 가진 노드를 꺼낸다.
            int cur = curNode.v;

            for (Node neighbor : adj[cur]) { // 현재 노드와 연결된 모든 이웃 노드를 탐색
                if (dist[neighbor.v] > dist[cur] + neighbor.w) { // 현재 발견된 경로가 기존에 알고 있던 경로보다 더 짧은지 확인
                    dist[neighbor.v] = dist[cur] + neighbor.w; // 발견 시 최단 경로 업데이트
                    pq.add(new Node(neighbor.v, dist[neighbor.v])); // 경로가 업데이트된 이웃 노드를 우선순위 큐에 추가한다.
                    // 이후 큐가 다시 정렬되어 다음 반복에서는 최단 경로를 가진 노드를 다시 탐색한다.
                }
            }
        }
        return dist; // start노드로부터 다른 모든 노드까지의 최단 경로가 저장된 dist 배열을 반환한다.
        // e.g. dist[i]에 start노드에서 i노드까지의 최단 경로가 저장된다.
    }
}