[백준] 최소비용 구하기 JAVA

 

반응형

728x90

[백준] 최소비용 구하기 - GOLD V 1916번

---

접근

• 플루이드-워셜 (시간 초과)
• 다익스트라 (Dijkstra's Algorithm)

---

풀이

N개의 도시에서 출발하는 M개의 버스를 통해 목표로 주어진 출발지에서 목적지까지 가는데 드는 비용의 최솟값을 구하는 문제이다. 이 문제는 가중치가 있는 방향 있는 그래프에서 최단 경로의 가중치를 구하는 문제이다. 저번에 풀었던 경로 찾기 문제에서 간단하게 설명했던 플루이드 워셜 알고리즘을 사용해서 풀려고 했으나 N의 최댓값이 1,000으로 플루이드-워셜 알고리즘을 사용할 경우 최악의 경우 10억의 연산이 발생해 주어지는 0.5초의 제한 시간 내 통과는 불가능하다. 플루이드-워셜은 모든 경로의 가중치를 다 구하다 보니 이번 문제에선 사용할 수 없는 방법이었다. 전체 코드 부분에 플루이드-워셜 알고리즘을 사용한 코드도 첨부는 해 놓겠다.

 

그렇다면 어떤 알고리즘을 사용해야 할까? 이 문제는 가중치가 있는 그래프이기 때문에 bfs를 사용하는 방법은 그렇게 좋지 않다. 그래프 이론에서 사용되는 최단 경로 알고리즘인 다익스트라 (Dijkstra's Algorithm) 알고리즘을 사용해야 한다. 음수 가중치를 가진 그래프에선 사용이 불가능하나 현재 문제는 양수의 가중치만 다루기 때문에 적합한 알고리즘이다. 

 

다익스트라 알고리즘은 출발지에서부터 각 노드들을 연결하며 점진적으로 최단 거리를 업데이트해 나가는 방식이다. 출발지 노드에서 연결된 최단 거리 노드를 검사하여 새로운 경로를 통해 도달할 수 있는 거리가 기존의 거리보다 짧은 경우 업데이트하게 된다.  예를 들어 1번 노드에서 3번 노드로 바로 가는 비용이 10이라고 가정할 때 바로 연결되어 있어 최단 경로처럼 보이지만 만약 1번 노드에서 2번을 거쳐 3번 노드로 가는 총비용이 10보다 작다면 2번 노드를 거쳐 3번 노드로 도착하는 경로가 최단 경로가 된다. 아래는 예시를 풀어서 적어 놓은 것이다.

경로: 1 -> 3 비용: 10

경로: 1 -> 2 비용: 2
경로: 2 -> 3 비용: 3
경로: 1 -> 2 -> 3 비용: 2 + 3 = 5

1 -> 3 최단 경로 = 1 -> 2 -> 3

이러한 방식으로 점진적인 최단 경로를 업데이트하며 목적지까지의 최단 경로를 얻게 되는 것이다. 

    private static class Node {
        private final int nodeIndex;
        private final int weight;

        public Node(int nodeIndex, int weight) {
            this.nodeIndex = nodeIndex;
            this.weight = weight;
        }
    }

 

노드 클래스를 정의한 것이다. 현재 노드의 번호와 가중치를 가지고 있다.

	int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

리스트를 2중으로 사용하여 그래프를 구현해 주었다. 각 인덱스가 노드를 나타내고 인덱스 값의 리스트가 연결된 노드들을 표현하는 것이다. 

	for (int m = 0; m < M; m++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int busCost = Integer.parseInt(input[2]);
            graph.get(start).add(new Node(end, busCost));
        }

입력받는 정점의 정보들로 그래프를 채워주는 과정이다. 출발지는 그래프의 인덱스이고 도착지는 출발지 인덱스의 리스트에 들어가게 된다.

	String[] startEnd = br.readLine().split(" ");
        int departure = Integer.parseInt(startEnd[0]);
        int arrival = Integer.parseInt(startEnd[1]);

        int[] costs = new int[N + 1];
        Arrays.fill(costs, Integer.MAX_VALUE);
        costs[departure] = 0;

문제에서 요구하는 출발지와 목적지를 변수에 할당하고 최소 비용 저장을 위한 배열을 선언했다. costs 배열에는 노드를 탐색하며 출발지에서 각 인덱스까지의 최단 비용이 들어가게 될 예정이다. 초기에는 연결되어있지 않은걸 나타내기 위해 무한대로 초기화해 주고 출발지는 0으로 초기화해 준다.

	PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Node(departure, 0));

우선순위 큐를 사용해 가중치가 낮은 노드부터 검사를 할 수 있게 해 줬다. 우선순위 결정 조건으로 가중치 오름차순을 설정해 준다. 큐에 시작값으로 출발지 노드가 들어가게 된다.

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

            if (node.weight > costs[node.nodeIndex]) {
                continue;
            }

            for (Node newNode : graph.get(node.nodeIndex)) {
                int newDistance = node.weight + newNode.weight;

                if (newDistance < costs[newNode.nodeIndex]) {
                    costs[newNode.nodeIndex] = newDistance;
                    pq.offer(new Node(newNode.nodeIndex, newDistance));
                }
            }
        }

큐를 사용해서 검사를 진행하는데 언뜻 보면 bfs로 푸는 거 같다. 큐에서 가중치가 가장 작은 노드를 꺼내고 노드의 가중치가 현재 해당 노드로 가는데 필요한 최소 비용보다 크다면 최단 경로가 아니기 때문에 넘어간다. 그렇지 않을 경우 해당 노드의 인접 노드를 그래프에서 모두 꺼내 인접 노드로 가는 비용을 더한다. 해당 노드로 가는 비용이 현재 존재하는 비용보다 작다면 해당 노드를 다음 경로로 큐에 추가하고 최소 비용을 최신화한다. 

	System.out.println(costs[arrival]);

배열 내 목적지 인덱스의 값이 최소 비용이 된다.

---

전체 코드 

다익스트라 (Dijkstra's Algorithm)

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

public class Main {
    private static class Node {
        private final int nodeIndex;
        private final int weight;

        public Node(int nodeIndex, int weight) {
            this.nodeIndex = nodeIndex;
            this.weight = weight;
        }
    }
    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());

        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int m = 0; m < M; m++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int busCost = Integer.parseInt(input[2]);
            graph.get(start).add(new Node(end, busCost));
        }

        String[] startEnd = br.readLine().split(" ");
        int departure = Integer.parseInt(startEnd[0]);
        int arrival = Integer.parseInt(startEnd[1]);

        int[] costs = new int[N + 1];
        Arrays.fill(costs, Integer.MAX_VALUE);
        costs[departure] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Node(departure, 0));

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

            if (node.weight > costs[node.nodeIndex]) {
                continue;
            }

            for (Node newNode : graph.get(node.nodeIndex)) {
                int newDistance = node.weight + newNode.weight;

                if (newDistance < costs[newNode.nodeIndex]) {
                    costs[newNode.nodeIndex] = newDistance;
                    pq.offer(new Node(newNode.nodeIndex, newDistance));
                }
            }
        }

        System.out.println(costs[arrival]);
        br.close();
    }
}

 

플루이드-워셜 (Floyd-Warshall)

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

public class Main {
    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());
        int[][] busRoutes = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            Arrays.fill(busRoutes[i], Integer.MAX_VALUE);
        }

        for (int i = 1; i <= N; i++) {
            busRoutes[i][i] = 0;
        }

        for (int m = 0; m < M; m++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int time = Integer.parseInt(input[2]);
            busRoutes[start][end] = Math.min(busRoutes[start][end], time);
        }

        String[] startEnd = br.readLine().split(" ");
        int departure = Integer.parseInt(startEnd[0]);
        int arrival = Integer.parseInt(startEnd[1]);

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (busRoutes[i][k] != Integer.MAX_VALUE && busRoutes[k][j] != Integer.MAX_VALUE &&
                            busRoutes[i][j] > busRoutes[i][k] + busRoutes[k][j]) {
                        busRoutes[i][j] = busRoutes[i][k] + busRoutes[k][j];
                    }
                }
            }
        }

        System.out.println(busRoutes[departure][arrival]);
        br.close();
    }
}