다익스트라 문제 정리

1번) 1753번 최단경로

1753번: 최단경로

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

public class BOJ_1753_1 {
    static int V, E, K;
    static ArrayList<Edge>[] graph;
    static boolean[] visited;
    static int[] dist;
    static PriorityQueue<Edge> pq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());

        graph = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        dist = new int[V + 1];
        pq = new PriorityQueue<>();

        for (int i = 0; i <= V; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i <= V; i++)
            dist[i] = Integer.MAX_VALUE;

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph[u].add(new Edge(v, w));
        }
        pq.add(new Edge(K, 0));
        dist[K] = 0;

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int curVertex = cur.vertex;

            if (!visited[curVertex]) {
                visited[curVertex] = true;
                for (int i = 0; i < graph[curVertex].size(); i++) {
                    Edge temp = graph[curVertex].get(i);

                    int nextV = temp.vertex;
                    int value = temp.value;

                    if (dist[nextV] > dist[curVertex] + value) {
                        dist[nextV] = dist[curVertex] + value;
                        pq.add(new Edge(nextV, dist[nextV]));
                    }
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            if (visited[i])
                System.out.println(dist[i]);
            else
                System.out.println("INF");
        }
    }

    static class Edge implements Comparable<Edge> {
        int vertex, value;  // 연결된 정점, 가중치 저장

        public Edge(int vertex, int value) {
            this.vertex = vertex;
            this.value = value;
        }

        @Override
        public int compareTo(Edge e) {
            return this.value - e.value;
        }
    }
}

 

2번) 2211번 네트워크 복구

2211번: 네트워크 복구

1번 문제는 방향그래프였다면, 2번 문제는 무방향그래프 문제이기에 Node 클래스 멤버 변수로 연결된 정점의 번호, 가중치 + 본인의 번호를 선언해줘야 한다.

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

public class Main {
    static ArrayList<Node>[] graph;
    static ArrayList<Node> ans;
    static boolean[] visited;
    static int[] dist;
    static PriorityQueue<Node> pq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        dist = new int[N + 1];
        pq = new PriorityQueue<>();
        ans = new ArrayList<>();

        for (int i = 0; i <= N; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i <= N; i++)
            dist[i] = Integer.MAX_VALUE;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            graph[s].add(new Node(s, e, t));
            graph[e].add(new Node(e, s, t));
        }
        pq.add(new Node(1, 1, 0));
        visited[1] = true;
        dist[1] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (!visited[cur.to]) {
                visited[cur.to] = true;
                ans.add(cur);
            }

            for (int i = 0; i < graph[cur.to].size(); i++) {
                Node next = graph[cur.to].get(i);

                if (dist[next.to] > dist[cur.to] + next.cost) {
                    dist[next.to] = dist[cur.to] + next.cost;
                    pq.add(new Node(next.from, next.to, dist[next.to]));
                }
            }
        }
        System.out.println(ans.size());
        for (Node node : ans)
            System.out.println(node.from + " " + node.to);
    }

    static class Node implements Comparable<Node> {
        int from, to, cost;
        
        Node(int start, int end, int cost) {
            this.from = start;
            this.to = end;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}