BJ G5 13424 비밀모임

BJ G5 13424 비밀모임

 

 

문제링크

http://www.acmicpc.net/problem/13424

13424번: 비밀 모임

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/AsC_OZfmdgM

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_G5_13424_비밀모임 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static int T;// 케스트 케이스
    static int N;// 방의 수: N (2 ≤ N ≤ 100) - 정점의 개수가 많지 않다 - 인접 행렬
    static int M;// 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)
    // 그래프 - 인접 행렬
    static int[][] graph;
    static int K;// 모임에 참여하는 친구의 수 K(1 ≤ K ≤ N)

    static int INF = 987654321;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        T = Integer.parseInt(input.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer tokens = new StringTokenizer(input.readLine(), " ");
            N = Integer.parseInt(tokens.nextToken());
            M = Integer.parseInt(tokens.nextToken());

            // 그래프 초기화
            graph = new int[N + 1][N + 1];
            for (int m = 0; m < M; m++) {
                tokens = new StringTokenizer(input.readLine(), " ");
                int a = Integer.parseInt(tokens.nextToken());
                int b = Integer.parseInt(tokens.nextToken());
                int c = Integer.parseInt(tokens.nextToken());

                graph[a][b] = graph[b][a] = c;
            }

            K = Integer.parseInt(input.readLine());

            // 어떤 점에서 다른 점들 까지의 최단 거리 - dijkstra 활용
            Edge[][] dijkstraResults = new Edge[K][];

            tokens = new StringTokenizer(input.readLine(), " ");
            for (int i = 0; i < K; i++) {
                dijkstraResults[i] = dijkstra(Integer.parseInt(tokens.nextToken()));
            }

            // 이제 각 정점별로 최소 비용을 찾아보면..
            int[] cumSums = new int[N + 1];
            for (int n = 1; n < cumSums.length; n++) {
                for (int k = 0; k < K; k++) {
                    cumSums[n] += dijkstraResults[k][n].cumCost;
                }
            }
            // System.out.println(Arrays.toString(cumSums));

            // 가장 작은 방 번호 출력
            int minVal = Integer.MAX_VALUE;
            int minIdx = 0;
            for (int i = cumSums.length - 1; i >= 1; i--) {
                if (cumSums[i] <= minVal) {
                    minVal = cumSums[i];
                    minIdx = i;
                }
            }
            output.append(minIdx).append("\n");
        }
        System.out.println(output);
    }

    static Edge[] dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        Edge[] dist = new Edge[N + 1];
        for (int i = 1; i < dist.length; i++) {
            dist[i] = new Edge(i, INF);
            if (i == start) {
                dist[i].cumCost = 0;
                pq.offer(dist[i]);
            }
        }

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

            for (int i = 1; i < graph.length; i++) {
                if (graph[front.no][i] != 0 && (dist[i].cumCost > dist[front.no].cumCost + graph[front.no][i])) {
                    dist[i].cumCost = dist[front.no].cumCost + graph[front.no][i];
                    pq.offer(dist[i]);
                }
            }
        }
        return dist;
    }

    static class Edge implements Comparable<Edge> {
        int no;
        int cumCost;

        public Edge(int no, int cumCost) {
            super();
            this.no = no;
            this.cumCost = cumCost;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.cumCost, o.cumCost);
        }

        @Override
        public String toString() {
            return "[no=" + no + ", cc=" + cumCost + "]";
        }
    }

    private static String src = "2\r\n" +
                                "6 7\r\n" +
                                "1 2 4\r\n" +
                                "1 3 1\r\n" +
                                "1 5 2\r\n" +
                                "2 3 2\r\n" +
                                "3 4 3\r\n" +
                                "4 5 2\r\n" +
                                "6 5 1\r\n" +
                                "2\r\n" +
                                "3 5\r\n" +
                                "4 5\r\n" +
                                "1 2 2\r\n" +
                                "1 3 1\r\n" +
                                "2 3 2\r\n" +
                                "2 4 3\r\n" +
                                "3 4 6\r\n" +
                                "2\r\n" +
                                "3 4";
}