다익스트라 > 1916번, 1238번

다익스트라 알고리즘 : 최단 경로 탐색 알고리즘

 

최단 거리는 여러 개의 최단 거리로 이루어져 있다

하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다

 

ex) 1번 노드부터 다른 모든 노드로 가는 최단 시간 경로

 

 

 

 

1916번

 

1번 도시에서 출발하여 다른 모든 도시들로 가는 최소 비용 경로

 

// 도시의 개수 = 노드 개수 (n)
// 버스의 개수 = 간선 개수 (m)
// 비용 = 가중치

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

public class beakjoon1916 {
    static int n;
    static int m;
    static boolean[] visited; // 노드 방문 여부 체크
    static ArrayList<Edge>[] lists; // 정점 간의 연결 정보를 나타내는 리스트
    static int[] costs;
    static int start;
    static int end;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        visited = new boolean[n + 1];
        costs = new int[n + 1];
        lists = new ArrayList[n + 1];

        for (int i = 1; i < n + 1; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            lists[start].add(new Edge(end, cost)); // 출발지, 도착지, 비용
        }
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        start = Integer.parseInt(st.nextToken()); // 출발점
        end = Integer.parseInt(st.nextToken()); // 최종 도착점
        Arrays.fill(costs, Integer.MAX_VALUE); // 큰 값으로 초기화
        dijkstra(start);
        System.out.println(costs[end]);
    }

    public static void dijkstra(int x) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Edge(x, 0)); // 시작 노드
        costs[x] = 0; // 출발점에 대한 최소 비용은 0
        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll(); // 비용이 가장 적은 노드를 꺼낸다
            if (!visited[edge.num]) {
                visited[edge.num] = true; // 꺼낸 노드는 방문 처리

                for (Edge next : lists[edge.num]) {
                    // 방문하지 않았고, 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
                    if (!visited[next.num] && costs[next.num] > edge.cost + next.cost) {
                        costs[next.num] = edge.cost + next.cost;
                        priorityQueue.offer(new Edge(next.num, costs[next.num]));
                    }
                }
            }
        }
    }
}

class Edge implements Comparable<Edge> {
    int num;
    int cost; // 비용

    Edge(int num, int cost) {
        this.num = num;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge e) {
        return this.cost - e.cost; // 최소 비용 탐색을 위한 비용 기준으로 오름차순 정렬
    }
}

 

 

1238번

 

 

1번 마을에 사는 학생이 다른 모든 마을들로 가는 최단 시간 경로

 

// 학생 N명 = 노드 개수
// M개의 단방향 도로들 = 간선 개수
// 소요 시간 = 가중치
// 자기 마을에서 x까지 갔다가 다시 자기 마을로 돌아온다 (왕복)
// [자기 마을 -> X의 최단 시간 거리] + [X -> 자기 마을의 최단 시간 거리]
// 각각의 학생들의 최단 시간 경로 구하기 > 그 중 가장 긴 시간이 걸리는 경우 출력

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

public class baekjoon1238 {

    static int n;
    static int m;
    static int x; // x를 반드시 거쳐야 함
    static boolean[] visited; // 노드 방문 여부 체크
    static ArrayList<Distance>[] lists; // 정점 간의 연결 정보를 나타내는 리스트
    static int[] times;


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

        times = new int[n + 1];
        lists = new ArrayList[n + 1];

        for (int i = 1; i < n + 1; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            lists[start].add(new Distance(end, time)); // 출발지, 도착지, 소요 시간
        }

        int [] arr = new int[n+1];

        for(int i = 1; i<=n; i++) { // 각각의 학생이 자기 마을에서 x까지 갔다가 다시 자기 마을로 돌아오는 거리들을 배열에 넣어준다
            dijkstra(i);
            int a = times[x];
            dijkstra(x);
            int b = times[i];
            arr[i] = a+b;
        }

        Arrays.sort(arr);
        System.out.println(arr[arr.length-1]);
    }

    public static void dijkstra (int x) {
        visited = new boolean[n + 1]; // 방문 여부 체크
        Arrays.fill(times, Integer.MAX_VALUE); // 큰 값으로 초기화

        PriorityQueue<Distance> priorityQueue = new PriorityQueue();
        priorityQueue.offer(new Distance(x, 0)); // 시작 노드
        times[x] = 0; // 출발점에 대한 최소 시간은 0

        while(!priorityQueue.isEmpty()) {
            Distance distance = priorityQueue.poll();
            if(!visited[distance.num]) {
                visited[distance.num] = true;
                for(Distance next : lists[distance.num]) {
                    if(times[next.num] > distance.time + next.time) {
                        times[next.num] = distance.time + next.time;
                        priorityQueue.offer(new Distance(next.num, times[next.num]));
                    }
                }
            }
        }

    }
}
class Distance implements Comparable<Distance> {
    int num;
    int time;

    Distance(int num, int time) {
        this.num = num;
        this.time = time;
    }

    @Override
    public int compareTo(Distance d) {
        return this.time-d.time; // 최단 경로를 구하기 위해 시간 기준으로 오름차순 정렬
    }
}