BOJ_1238 : 파티

👉 문제링크

1238번: 파티

---

---

🔸 문제 분석 🔸

• N명의 사람과 M개의 도로가 있다.
  • X번 사람의 집에 모두가 최단거리로 모이고 집에 갈 때, 소요시간의 최대 값을 출력한다.
  • 각 집 사이의 도로는 단방향 연결이다.
• 최단거리를 구하고 그 중 최대 값을 찾아야 한다.
  • 각자 집에서 파티로 갈 때는 각각의 최단 거리를 구해야 하므로, 다익스트라 알고리즘을 N-1번 반복한다.
  • 파티에서 집으로 돌아갈 때는 시작 노드에서 다른 모든 노드로의 최단 거리를 구해야 하므로, 프림 알고리즘을 사용한다. (또는 다익스트라 알고리즘을 N-1번 반복한다)

🔸 코드 🔸

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

public class Main {
    private static class Edge implements Comparable<Edge> {
        int node, weight;

        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    private static int N, M, X;
    private static ArrayList<Edge>[] adjList;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 학생(집) 수
        M = Integer.parseInt(st.nextToken()); // 도로 수
        X = Integer.parseInt(st.nextToken()); // 파티 집 번호

        adjList = new ArrayList[N + 1]; // 인접 리스트 : 다익스트라용

        for (int i = 1; i <= N; i++) {
            adjList[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());

            Edge temp = new Edge(end, time);
            adjList[start].add(temp);
        }

        // Prim
        int[] goToHome = new int[N + 1];
        Arrays.fill(goToHome, Integer.MAX_VALUE);

        PriorityQueue<Edge> pq = new PriorityQueue<>(); // 우선순위 큐 : 프림용
        visited = new boolean[N + 1];

        pq.add(new Edge(X, 0));

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

            if (visited[now.node]) continue; //이미 방문 한 노드면 다시 뽑기

            visited[now.node] = true;
            goToHome[now.node] = now.weight;

            for (Edge e : adjList[now.node]) {
                if (!visited[e.node]) {
                    pq.add(new Edge(e.node, e.weight + goToHome[now.node]));
                }
            }
        }
//        System.out.println(Arrays.toString(goToHome));

        // Dijkstra
        int[] goToParty = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            if (i == X)
                goToParty[i] = 0;
            else
                goToParty[i] = dijkstra(i, X);
        }
//        System.out.println(Arrays.toString(goToParty));

        // Output
        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, goToHome[i] + goToParty[i]);
        }

        bw.write(Integer.toString(max));
        bw.flush();
    }

    private static int dijkstra(int start, int end) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        dist[start] = 0;
        pq.add(new Edge(start, 0));

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

            for (Edge e : adjList[now.node]) {
                int nw = now.weight + e.weight;
                if (dist[e.node] > nw) {
                    dist[e.node] = nw;
                    pq.add(new Edge(e.node, nw));
                }
            }
        }

        return dist[end];
    }
}

🔸 코드 해석 🔸

• 노드의 연결 정보를 인접 리스트 adjList에 저정한다.
• Prim 알고리즘으로 X번 집에서 각자의 집으로 가는 최단 거리를 계산해 goToHome 배열에 저장한다.
• Dijkstra 알고리즘으로 각자의 집에서 X번 집에 오는 최단 거리를 계산해 goToParty 배열에 저장한다.
  • n-1번 dijkstra 메서드를 호출해 계산을 반복한다.

---

🔸 end 🔸

• 최단 거리를 계산해야 한다는 것도 일찍 파악하고, 다익스트라와 프림 선택도 바로 생각났지만 알고리즘의 구현에 시간이 많이 들었다.
  • 아직 알고리즘 학습과 연습이 더 필요한 것 같다.