다익스트라 알고리즘

1. 인접 행렬

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class DijkstraTest2_PQ {
 
    static class Vertex implements Comparable<Vertex> {
        int no, minDistance; // 정점의 번호, 출발지에서 자신으로의 최소 비용
 
        public Vertex(int no, int minDistance) {
            this.no = no;
            this.minDistance = minDistance;
        }
 
        @Override
        public int compareTo(Vertex o) {
            return this.minDistance - o.minDistance;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(in.readLine());
        int[][] adjMatrix = new int[V][V];
        int start = 0;
 
        for (int i = 0; i < V; i++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int j = 0; j < V; j++) {
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        int[] distance = new int[V]; // 출발지에서 자신으로 오는 최소비용
        boolean[] visited = new boolean[V]; // 최소비용 확정여부
        PriorityQueue<Vertex> pQueue = new PriorityQueue<>();
 
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0; // 출발지 0
        pQueue.offer(new Vertex(start, distance[start]));
 
        while (!pQueue.isEmpty()) {
            // 단계1 : 최소비용이 확정되지 않은 정점 중 최소비용의 정점 선택
            Vertex current = pQueue.poll();
 
            if (visited[current.no]) // 중복 제거
                continue;
 
            visited[current.no] = true;
//            if (current == end) // 목적 지점이 있을 경우
//                break;
 
            // 단계2 : 선택된 정점을 경유지로 하여 아직 최소비용이 확정되지 않은 방문할 수 있는 다른 정점의 최소비용을 고려
            for (int j = 0; j < V; j++) {
                if (!visited[j] && adjMatrix[current.no][j] != 0
                        && distance[j] > distance[current.no] + adjMatrix[current.no][j]) {
                    distance[j] = distance[current.no] + adjMatrix[current.no][j];
                    pQueue.offer(new Vertex(j, distance[j]));
                }
            }
        }
        System.out.println(Arrays.toString(distance));
    }
}
 

 

2. 인접 리스트

1) 최단경로 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

import java.io.*;
import java.util.*;
 
public class Main {
    static class Node implements Comparable<Node> {
        int vertex;
        int weight;
 
        public Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken()); // 정점의 수
        int E = Integer.parseInt(st.nextToken()); // 간선의 수
        int K = Integer.parseInt(br.readLine()); // 시작 정점
        List<PriorityQueue<Node>> allRoute = new ArrayList<PriorityQueue<Node>>();
 
        for (int i = 0; i < V + 1; i++) { // 정점에 대한 링크 객체 생성
            allRoute.add(new PriorityQueue<>());
        }
        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 weight = Integer.parseInt(st.nextToken());
            PriorityQueue<Node> route = allRoute.get(from); // 우선순위 큐를 이용하여 경로 전부 삽입
            route.offer(new Node(to, weight));
        }
        int[] distance = new int[V + 1];
        boolean[] visited = new boolean[V + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[K] = 0; // 시작 지점 거리 0 설정
        PriorityQueue<Node> pQueue = new PriorityQueue<>();
        pQueue.offer(new Node(K, distance[K]));
        while (!pQueue.isEmpty()) {
            Node current = pQueue.poll(); // 최소 가중치 바로 탐색
 
            if (visited[current.vertex]) // 중복 제거
                continue;
            visited[current.vertex] = true;
 
            PriorityQueue<Node> linkQ = allRoute.get(current.vertex);
            while (!linkQ.isEmpty()) { // 이제 방문하지 않을 것이므로 큐를 비워도 상관이 없음
                Node link = linkQ.poll();
                if (!visited[link.vertex]) { // 가중치가 더 낮을 경우에만 갱신
                    if (distance[link.vertex] > distance[current.vertex] + link.weight)
                        distance[link.vertex] = distance[current.vertex] + link.weight;
                    pQueue.offer(new Node(link.vertex, distance[link.vertex]));
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (distance[i] == Integer.MAX_VALUE)
                sb.append("INF\n");
            else
                sb.append(distance[i]).append("\n");
        }
        System.out.println(sb);
    }
}
 

 

2) 해킹 : https://www.acmicpc.net/problem/10282

10282번: 해킹

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int n, d, c;
    static List<List<int[]>> link;
    static StringBuilder sb = new StringBuilder();
 
    static void dijkstra() {
        // 현재 컴퓨터 번호, 현재 컴퓨터까지 도달하는데 걸리는 시간
        Queue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) { // 걸리는 시간 오름차순 정렬
                return o1[1] - o2[1];
            }
        });
        pq.offer(new int[] { c, 0 });
 
        boolean[] visited = new boolean[n + 1]; // 방문 여부
        int[] minTime = new int[n + 1]; // 컴퓨터에 도달하는데 걸리는 최소 시간
        Arrays.fill(minTime, Integer.MAX_VALUE / 2);
        minTime[c] = 0;
        int cnt = 0, maxTime = 0;
 
        while (!pq.isEmpty()) {
            int[] pollArr = pq.poll();
            int num = pollArr[0];
            int time = pollArr[1];
 
            if (visited[num]) // 이미 방문한 경우
                continue;
 
            visited[num] = true; // 방문 처리
            maxTime = Math.max(maxTime, time); // 도달한 컴퓨터의 최대 감염시간 갱신
            cnt++;
 
            for (int[] li : link.get(num)) {
                // 방문하지 않았으면서 걸리는 시간이 더 짧아지는 경우
                if (!visited[li[0]] && minTime[li[0]] > minTime[num] + li[1]) {
                    minTime[li[0]] = minTime[num] + li[1];
                    pq.offer(new int[] { li[0], minTime[li[0]] });
                }
            }
        }
        sb.append(cnt).append(" ").append(maxTime).append("\n");
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
 
            // link 초기화
            link = new ArrayList<>(); // 현재 컴퓨터를 의존하는 컴퓨터 번호, 감염되는데 걸리는 시간
            for (int i = 0; i <= n; i++) {
                link.add(new ArrayList<>());
            }
 
            // 의존성 추가
            for (int i = 0; i < d; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());
                link.get(b).add(new int[] { a, s }); // 컴퓨터 b를 의존하는 컴퓨터 a추가
            }
 
            dijkstra();
        }
        System.out.println(sb);
    }
}