BAEK13424. 비밀 모임

2023년 6월 22일

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

시간 : ❤❤❤❤❤

만족도 : ❤❤❤❤❤

---

전형적인 다익스트라 알고리즘 문제이다.

다익스트라 메소드를 만들어준 뒤,

모임에 참여하는 친구들을 다익스트라 메소드의 인자값에 넣어주고,

노드의 수만큼 배열을 생성해서 다 더해주었다.

그 중에서 가장 작은 값을 찾되, 작은 값이 여러 개일 경우 숫자가 작은 노드를 출력했다.

---

• 코드

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;
  
    public class BAEK13424 {
        static class Node implements Comparable<Node> {
            int end;
            int cost;
  
            public Node (int end, int cost) {
                this.end = end;
                this.cost = cost;
            }
  
            @Override
            public int compareTo(Node o) {
                return this.cost - o.cost;
            }
        }
        static int N, M, K;
        static List<Node>[] list;
        static int[] dist;
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;
            StringBuilder sb = new StringBuilder();
            int T = Integer.parseInt(br.readLine());
            for (int tc = 0; tc < T; tc++) {
                st = new StringTokenizer(br.readLine());
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());
                list = new ArrayList[N+1];
  
                for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();
  
                for (int i = 0 ; i < M; i++) {
                    st = new StringTokenizer(br.readLine());
                    int from = Integer.parseInt(st.nextToken());
                    int to = Integer.parseInt(st.nextToken());
                    int cost = Integer.parseInt(st.nextToken());
                    list[from].add(new Node(to, cost));
                    list[to].add(new Node(from, cost));
                }
  
                K = Integer.parseInt(br.readLine());
                st = new StringTokenizer(br.readLine());
                int[] ans = new int[N+1];
                for (int i = 0; i < K; i++) {
                    int friend = Integer.parseInt(st.nextToken());
                    dijkstra(friend);
                    for (int j = 1; j <= N; j++) {
                        ans[j] += dist[j];
                    }
                }
                int result = Integer.MAX_VALUE;
                int res = 0;
                for (int i = 1; i <= N; i++) {
                    if (ans[i] < result) {
                        result = ans[i];
                        res = i;
                    }
                }
                sb.append(res).append("\n");
            }
            System.out.println(sb.toString());
        }
        public static void dijkstra(int start) {
            dist = new int[N+1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            // 우선순위큐 선언 및 초기화
            // cost가 작은 순서로 뽑을 수 있도록 하기 위함.
            PriorityQueue<Node> q = new PriorityQueue<>();
            // 방문 배열 선언 및 초기화
            boolean[] check = new boolean[N+1];
            q.add(new Node(start, 0));
            dist[start] = 0;
  
            while(!q.isEmpty()) {
                // cost가 작은 순으로
                Node curNode = q.poll();
                int cur = curNode.end;
  
                // 방문했다면 continue
                if(check[cur] == true) continue;
                check[cur] = true;
  
                for (Node node : list[cur]) {
                    if (dist[node.end] > dist[cur] + node.cost) {
                        dist[node.end] = dist[cur] + node.cost;
                        q.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
        }
    }