1916번 - 다익스트라 알고리즘(Comparable 클래스)

다익스트라 알고리즘을 사용해 가장 비용이 싼 경로를 찾는 문제였다.

출발지와 목적지가 주어졌고, 각 경로의 가격이 주어졌다.

처음엔 다익스트라를 이용하지 않아 시간초과가 되었고 해당 코드는 아래와 같다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 최소비용구하기_1916번_시간초과 {
    static int N, M;
    static List<Integer>[] listArray;
    static int[][] fees;
    static boolean[] visited;
    static int start, end;
    static int min = 100000000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        listArray = new List[N+1];
        for (int i = 0; i <= N; i++) {
            listArray[i] = new ArrayList<>();
        }
        fees = new int[N+1][N+1];
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int fee = sc.nextInt();
            listArray[s].add(e);
            fees[s][e] = fee;
        }
        start = sc.nextInt();
        end = sc.nextInt();

        visited = new boolean[N+1];
        visited[start] = true;
        minimumCost(start, 0);

        System.out.println(min);

    }

    static void minimumCost(int city, int sum) {
        if (sum >= min) {
            return;
        }
        if (city == end) {
            min = Math.min(sum, min);
        }
        for (int i = 0; i < listArray[city].size(); i++) {
            int next = listArray[city].get(i);
            if(!visited[next]) {
                visited[next] = true;
                minimumCost(next, sum + fees[city][next]);
                visited[next] = false;
            }
        }
    }
}

또 재귀를 이용하여 풀었고, 정말 다익스트라 알고리즘이 생각나지 않았기 때문이다.
단지 지금 위치한 곳까지의 거리와 목적지까지 직접적인 거리를 계속 더해주며 최솟값을 구했다.

하지만 이는 정말 비효율적인 방법이고, 이딴 방법이라면 지금의 네비게이션은 나오기 어려웠을 것이다.

아래는 다익스트라 알고리즘을 다시 한번 공부한 후 작성한 코드이다.

import java.util.*;

// Edge 클래스: e와 fee 쌍을 저장하는 클래스
class Edge implements Comparable<Edge> {
    int e;
    int fee;

    public Edge(int e, int fee) {
        this.e = e;
        this.fee = fee;
    }

    // fee 값을 기준으로 오름차순 정렬
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.fee, other.fee);
    }
}

public class 최소비용구하기_1916번 {
    static int N, M;
    static List<PriorityQueue<Edge>> routes;
    static int start, end;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 노드 수
        M = sc.nextInt(); // 간선 수

        // routes 리스트 초기화
        routes = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            routes.add(new PriorityQueue<>()); // 기본 설정으로 최소 힙
        }

        // 입력 받아서 routes에 저장
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int fee = sc.nextInt();
            routes.get(s).add(new Edge(e, fee));
        }

        start = sc.nextInt();
        end = sc.nextInt();
        visited = new boolean[N+1];
        visited[start] = true;

        int min = minimumFee();
        System.out.println(min);
    }

    static int minimumFee() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            if (now.e == end) {
                return now.fee;
            }
            visited[now.e] = true;
            for (Edge next : routes.get(now.e)) {
                if (!visited[next.e]) {
                    pq.add(new Edge(next.e, now.fee + next.fee));
                }
            }
        }
        return -1;
    }
}

지금 위치에서 직접 갈 수 있는 경로를 우선순위 큐에 저장한 후,
가장 가격이 싼 곳을 선택해, 해당 경로와 경로에 대한 가격을 저장하며 이동하는 원리이다.

한 정점에서 다른 정점으로 이동해 직접 갈 수 있는 곳을 우선순위 큐에 저장할 때,
새로운 큐가 아닌 기존의 큐에 저장한다. 

Edge라는 클래스를 만든 것을 볼 수 있는데,
이 Edge 객체의 fee 요소에 해당 경로까지의 요금을 계속 더해주며 이동하고,
더해진 값과 기존의 값들과의 비교가 계속해져 이뤄진다.
결국 목적지까지 가장 빨리 도착하는 경로는 다른 경로들과의 가격 경쟁을 이긴 경로로, 가장 싼 경로이다.

한 학기 전에 프로젝트에서 길찾기 시스템을 설계하며, 다익스트라에 대한 공부를 했는데도,
다익스트라를 까먹었다는 것을 알 수 있었다.

더 꾸준하게 알고리즘, 자료구조 공부를 해야겠다.