백준 1446 : 지름길 [JAVA]

[문제 링크]

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

[난이도]

- Silver 1

 

[알고리즘]

- DP

- 다익스트라

 

[코드]

import java.util.*;

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

        int N = scanner.nextInt(); // 지름길의 개수
        int D = scanner.nextInt(); // 고속도로의 길이

        // graph를 생성하고 초기화
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= D; i++) {
            graph.add(new ArrayList<>()); // 노드의 개수만큼 생성
        }

        // 지름길 정보를 graph에 추가
        for (int i = 0; i < N; i++) {
            int u = scanner.nextInt(); // 시작 노드
            int v = scanner.nextInt(); // 도착 노드
            int w = scanner.nextInt(); // 가중치
            if (v <= D) { // 노드범위 이상일경우 추가하지 않는다.
                graph.get(u).add(new int[]{v, w}); //
            }
        }

        int[] dist = new int[D + 1]; // 가중치를 기록할 배열
        Arrays.fill(dist, Integer.MAX_VALUE); // 초기값은 모두 INF
        dist[0] = 0; // 시작 위치는 0

        // int[] a 중에서 두번째 요소인 a[1]을 기준으로 큐를 정렬, 즉 가중치(비용)을 기준으로 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{0, 0}); // {현재 위치, 현재 비용}

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentPos = current[0];
            int currentCost = current[1];

            // 만약 현재 비용이 기록된 비용보다 크다면, 이미 더 적은 비용으로 도달한 경로가 존재하므로 무시
            if (currentCost > dist[currentPos]) continue;

            // 다음 지점으로 이동 (일반 도로, 현재 위치에서 한 칸 앞으로 이동)
            // 현재위치에서 한 칸 앞으로 이동한 위치가 D(도로의 길이, 간선의 범위)를 넘지않는경우
            // 현재위치에서 한칸 앞으로 이동한 위치까지의 비용이 기존에 기록된 비용보다 작은 경우
            if (currentPos + 1 <= D && currentCost + 1 < dist[currentPos + 1]) {
                dist[currentPos + 1] = currentCost + 1; // 다음 위치까지의 비용 갱신
                pq.add(new int[]{currentPos + 1, currentCost + 1}); // 우선순위 큐에 추가
            }

            // 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
            for (int[] edge : graph.get(currentPos)) {
                int nextPos = edge[0]; // 지름길의 도착 위치
                int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
                // 지름길을 이용한 비용이 더 적다면 비용 갱신
                if (nextCost < dist[nextPos]) {
                    dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
                    pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
                }
            }
        }

        System.out.println(dist[D]);
    }
}

[풀이]

일반적인 다익스트라 알고리즘과 같다. 하지만 추가된 부분이 있다.

// 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
            for (int[] edge : graph.get(currentPos)) {
                int nextPos = edge[0]; // 지름길의 도착 위치
                int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
                // 지름길을 이용한 비용이 더 적다면 비용 갱신
                if (nextCost < dist[nextPos]) {
                    dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
                    pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
                }

 

지름길을 이용한 경우의 가중치를 한번 더 생각해주어야 한다는 것이다.