[Algo] 백준 12834 주간미팅 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/12834

메모리 : 22500KB

시간 : 464ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static class Node {
        int idx;
        int cost;

        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }

    static int N, V, E, kist, cr, ans;
    static ArrayList<ArrayList<Node>> list;

    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());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        kist = Integer.parseInt(st.nextToken());
        cr = Integer.parseInt(st.nextToken());

        int[] home = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            home[i] = Integer.parseInt(st.nextToken());
        }
        // 인접리스트 만들기
        list = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            list.add(new ArrayList<>());
        }
        // 그래프에 값 추가
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(x).add(new Node(y, c));
            list.get(y).add(new Node(x, c));
        }
        ans = 0;
        for (int i = 0; i < N; i++) {
            dijkstra(home[i], kist);
            dijkstra(home[i], cr);
        }
        System.out.println(ans);

    }

    private static void dijkstra(int start, int end) {
        // 노드의 개수만큼 방문 체크
        boolean[] check = new boolean[V + 1];
        // 값을 저장할 dp배열
        int[] dist = new int[V + 1];
        // 최댓값으로 초기화
        for (int i = 0; i < V + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        // 시작값은 0 : 자기 자신을 본다고 여기기 때문에.
        dist[start] = 0;
        // 모든 노드를 돌면서 가장 가까운 노드를 선택해 이동한다.
        for (int i = 0; i < V; i++) {
            int nodevalue = Integer.MAX_VALUE;
            int nodeidx = 0;
            for (int j = 0; j < V + 1; j++) {
                // 방문하지 않았고 최소값이 갱신되어야 하면
                if (!check[j] && dist[j] < nodevalue) {
                    nodevalue = dist[j];
                    nodeidx = j;
                }
            }

            // 선택된 노드 방문처리
            check[nodeidx] = true;
            // 선택된 노드의 인접노드 값 갱신
            for (int j = 0; j < list.get(nodeidx).size(); j++) {
                Node n = list.get(nodeidx).get(j);
                // 원래 값과 새 값을 비교해 작은 값으로 갱신
                if (dist[n.idx] > dist[nodeidx] + n.cost) {
                    dist[n.idx] = dist[nodeidx] + n.cost;
                }
            }
        }
        if (dist[end] == Integer.MAX_VALUE) {
            ans -= 1;
        } else {
            ans += dist[end];
        }
    }

}

코드

전형적인 다익스트라문제! 싸피강의 다시 들으며 다익스트라 공부해서 풀었다.
다익스트라는 "그래프 탐색을 그리디로" 라는 말씀 하나로 이해가 잘 됐다.