[백준] 1916: 최소비용 구하기 (다익스트라 알고리즘) - JAVA

class 4

https://www.acmicpc.net/problem/1916

 

 

 

 

# 문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

# 예제

입력 : 

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

 

출력 :  첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

4

 

# 필요개념

이 문제는 최단경로를 구하는 문제라고 이해하면 된다. 최소한의 비용으로 원하는 목적지로 갈 수 있도록 문제를 풀어내면 된다. 원래는 완전탐색으로 문제풀이를 진행했으나 1%에서 시간초과가 발생하였다. 아래 코드가 해당 코드이다. (1%에서 시간초과가 발생해서 맞는 코드인지도 모르겠다. 예제만 패스한 코드 ..)

import java.io.*;
import java.util.*;
public class Main {
    static Map<Integer, List<int[]>> inputs = new HashMap<>();
    static boolean[] isVisit;
    static int end;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        isVisit = new boolean[N + 1];

        // 리스트 생성
        for (int i = 1 ; i <= N ; i++) {
            inputs.put(i, new LinkedList<>());
        }

        // 값 대입
        for (int i = 1 ; i <= M ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int key = Integer.parseInt(st.nextToken());
            inputs.get(key).add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        minVal(start, 0);
        System.out.println(min);
    }

    private static void minVal(int start, int value) {
        List<int[]> list = inputs.get(start);
        for (int i = 0 ; i < list.size() ; i++) {
            int willGo = list.get(i)[0];
            if (willGo == end) {
                if (min > value + list.get(i)[1]) min = value + list.get(i)[1];
                return;
            }
            if (!isVisit[willGo]) {
                isVisit[willGo] = true;
                minVal(willGo, value + list.get(i)[1]);
                isVisit[willGo] = false;
            }
        }
    }
}

 

 

보기좋게 실패한 후 다른 사람들의 방식을 둘러보았고, 잊고있던 알고리즘들이 생각났다 ! 나는 그중 다익스트라 알고리즘을 이용해 풀었고, 내친김에 다양한 알고리즘을 찾아보며 복기했다.

 

 ✅ 최단경로를 탐색하는 알고리즘

1. 완전탐색 알고리즘

가중치가 없는 그래프, 바꿔말해 가중치를 신경쓰지 않고 최소 이동횟수를 구하는 문제에서 효율적으로 이용할 수 있는 알고리즘이다. 난 완전 잘못 이용한 것이었다 .. 😊 

 

2. 다익스트라 알고리즘

다익스트라 알고리즘은 가중치를 저장하는 테이블(배열)을 사용하여 최저 가중치를 갱신해 저장해나간다. 노드 방문 순서는 가중치가 작은 노드를 먼저 방문하기 때문에 가중치가 작은 노드를 먼저 방문할 수 있게 우선순위 큐를 사용해 구현한다. 

 

아래 링크는 아주아주 간단하게 옛날에 정리한 게시글이다.

https://wanna-developer02.tistory.com/53

[알고리즘] CHAP 4. GA - Dijkstra's algorithm (다익스트라 알고리즘)

 

 🌟우선순위 큐의 조건을 어떻게 설정해야할지 몰라서 찾아보았는데, 노드 클래스를 생성할 때 Comparable<> 인터페이스를 상속하면 compareTo 메소드를 제공받을 수 있다 ! 여기에서 우선순위 큐의 조건을 설정할 수 있었다.

 

3. 플로이드-워셜 알고리즘

반쯤 잊고있던 알고리즘이었다. 동적계획법으로 접근해서 모든 경유 정점에 대해 시작점과 도착점을 탐색한다. 음수사이클 존재 여부도 알 수 있기 때문에 음수 가중치를 갖는 그래프에서도 적용할 수 있다는 장점이 있지만, 삼중 반복문을 사용하여 시간복잡도가 O(N^3)이 된다..

 

 

이 외에도 처음 들어보는 알고리즘이 많았다. 아래 글을 참고해서 조사해보았다.

https://devluce.tistory.com/19

[알고리즘] 최단 경로 알고리즘 비교 및 사용 케이스 정리

 

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    static List<List<Node>> list = new LinkedList<>();
    static boolean[] isVisit;
    static int[] weight;
    static int end;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        isVisit = new boolean[N + 1];
        weight = new int[N + 1];

        // 리스트 생성
        for (int i = 0 ; i <= N ; i++) {
            list.add(new LinkedList<>());
            weight[i] = Integer.MAX_VALUE;
        }

        // 값 대입
        for (int i = 1 ; i <= M ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int key = Integer.parseInt(st.nextToken());
            Node node = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            list.get(key).add(node);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        System.out.println(dijkstra(start));
    }

    private static int dijkstra(int start) {
        Queue<Node> queue = new PriorityQueue<>();
        weight[start] = 0;
        queue.add(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node nowNode = queue.poll();
            int now = nowNode.end;

            if (!isVisit[now]) {
                isVisit[now] = true;
                List<Node> nowList = list.get(now);
                for (Node node : nowList) {
                    if (!isVisit[node.end] && weight[node.end] > weight[now] + node.weight) {
                        weight[node.end] = weight[now] + node.weight;
                        queue.add(new Node(node.end, weight[node.end]));
                    }
                }
            }
        }
        return weight[end];
    }
}

class Node implements Comparable<Node> {
    int end;
    int weight;
    
    Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

 

# 결과