[백준] 1916 최소비용 구하기 (Java)

✉️문제

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

1916번: 최소비용 구하기

 

📝 접근

그래프 알고리즘 중 다익스트라 알고리즘을 이용하였다. 다음의 문장에서 다익스트라 알고리즘을 이용해야겠다는 생각이 들었다.

 A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라." 

 

다익스트라 알고리즘은 최단 경로 탐색 알고리즘으로 한 정점에서 모든 정점으로 가는 최단 경로를 구할 수 있다. 만약 문제에서 한 정점에서 모든 경로로의 최단 경로를 각각 구하라고 하면 다익스트라 알고리즘을 이용할 수 있다.

 

❗다익스트라 알고리즘을 구현하는 방법 

1. dis 배열을 Integer.MAX_VALUE로 초기화한다. 이 배열에 각 정점으로 가는 비용을 저장할 것이다.
2. 시작점을 잡은 뒤 dis[시작점] = 0으로 초기화한다.
3. dis 배열에서 최솟값을 찾은 뒤 이 정점에서 갈 수 있는 정점들 방문한다. (for문을 이용하면 O(n)이지만 우선순위 큐를 이용하면 log n이 된다)
4. 만약 현재 dis[갈 수 있는 정점]이 정점까지 가는데 드는 비용보다 크다면 이를 업데이트 한다.
5. 3 ~ 4를 반복한다. 

 

🗝 문제풀이

package step2;


import java.util.*;

public class Q1916 {

    static int[] dis;

    public static class Node implements Comparable<Node>{
        int now, cost;

        public Node(int now, int cost) {
            this.now = now;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 도시의 개수
        int m = sc.nextInt(); // 버스의 수

        // ArrayList를 초기화한다.
        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        for(int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        // 입력 받기
        for(int i = 1; i <= m; i++) {
            int s = sc.nextInt(); // 출발지
            int d = sc.nextInt(); // 도착지
            int c = sc.nextInt(); // 비용
            list.get(s).add(new Node(d, c));
        }

        
        dis = new int[n + 1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        
        int start = sc.nextInt();
        int end = sc.nextInt();

        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 시작점을 우선순위 큐에 넣는다.
        pq.add(new Node(start, 0)); 
        dis[start] = 0;
        
        while(!pq.isEmpty()) {
            // 가장 작은 수를 꺼낸다.
            Node node = pq.poll();
            int now = node.now;
            int nowCost = node.cost;
            
            // 정점까지 오는 비용이 다른 루트로 방문하는 비용보다 비싸면 넘어간다. (최적화)
            if(nowCost > dis[now]) continue;
            
            for (Node next : list.get(now)) {
                // 다음 정점 현재 최소 비용이 현재 정점에서 다음 정점으로 가는 비용보다 크면 이를 업데이트한다.
                if(dis[next.now] > next.cost + nowCost) {
                    dis[next.now] = next.cost + nowCost;
                    pq.add(new Node(next.now, next.cost + nowCost));
                }
            }
        }

        System.out.println(dis[end]);

    }
}

 

생각해볼만한 테스트 케이스

1. 현재 정점에서 다음 정점으로 가는 경우의 수는 여러개가 될 수 있다. 만약에 배열을 이용해서 구현했다면 여기서 실수 할 확률이 많다.

Ex ) 1번 정점에서 2번 정점으로 가는 비용이 2개일 수 있다. (1, 2, 3) / (1, 2, 5) 

 

2. 시간초과가 발생한다면 if(nowCost > dis[now]) continue 부분을 확인하자. 현재 정점까지의 비용이 다른 루트를 통해 온 비용보다 비싸다면 우선순위 큐에 넣을 필요가 없다. -> 다익스트라의 전제 조건은 가중치에 마이너스가 없기 때문이다.