[BOJ] 백준 12834 : 주간 미팅 (java)

🧪 12834 주간 미팅

---

난이도 : 🌟 골드 4
유형 : 다익스트라

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

 

📝 문제

---

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이때 Σdi의 값을 출력하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

 

출력

 

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

 

🧐 핵심 로직 

---

1) 주어진 입력값을 변수 선언을 통해 받아준다.

 

2) 출발 노드와 도착 노드, 거리값을 대입해준다.

 

3) 팀원의 위치마다 다익스트라 함수가 반복되도록 하고 반복하는 동안 거리 배열과 방문 배열을 초기화 시켜준다.

 

4) 다익스트라 함수 내부에선 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.

 

5) 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.

 

6) 다익스트라 함수가 끝나면 KIST와 씨알푸드까지의 거리를 계산해서 res에 추가하고 다른 팀원의 위치에 대해 3 ~ 6의 과정을 반복한다.

 

💻 최종 코드 (484 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static class Node implements Comparable<Node> {
        int to, dist;

        Node(int to, int dist) {
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

    static int n, v, e, a, b, res;
    static int INF = 987654321;
    static int[] positions;
    static int[] dist;
    static boolean[] visited;
    static List<List<Node>> graph;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        positions = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            positions[i] = Integer.parseInt(st.nextToken());
        }

        graph = new ArrayList<>();
        for (int i = 0; i < e; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());

            graph.get(from).add(new Node(to, dist));
            graph.get(to).add(new Node(from, dist));
        }

        for (int position : positions) {
            dijkstra(position);

            dist[a] = dist[a] == INF ? -1 : dist[a];
            dist[b] = dist[b] == INF ? -1 : dist[b];
            res += dist[a] + dist[b] ;
        }

        System.out.println(res);

        br.close();
    }

    private static void dijkstra(int start) {

        dist = new int[v + 1];
        visited = new boolean[v + 1];
        Arrays.fill(dist, INF);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            visited[now.to] = true;

            for (Node next : graph.get(now.to)) {

                if (!visited[next.to] && dist[next.to] > dist[now.to] + next.dist) {
                    dist[next.to] = dist[now.to] + next.dist;
                    pq.add(new Node(next.to, dist[next.to]));
                }
            }

        }
    }
}