[Boj_1446] 지름길

📎 문제 링크

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

1446번: 지름길

 

▸ 문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

 

▸ 입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

 

▸ 출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 1
• 🔔  문제 유형 : 그래프 이론, 데이크스트라, 최단 경로
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 지름길에 대한 정보를 인접 리스트에 저장해 주었는데,
• 이때 지름길이 목표지점을 넘어서거나(역주행 불가), 기존 길보다 거리가 긴 경우는 제외하고 리스트에 저장했다.
• dist 배열에는 거리를 시작 지점에서 1씩 증가하며 해당 지점으로 가는 지름길이 있을 때, 더 짧게 이동할 수 있는 경우 최단 거리를 갱신했다.

 

✔ 최종 코드

메모리 : 12564KB
시간 : 92ms

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, d;
    static ArrayList<ArrayList<pos>> list;
    static int[] dist;
    static boolean[] checked;
    static public class pos implements Comparable<pos> {
        int end; int dist;

        public pos(int end, int dist) {
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(pos o) {
            return this.dist - o.dist;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 지름길의 개수
        d = Integer.parseInt(st.nextToken()); // 고속도로의 길이

        // 인접 리스트
        list = new ArrayList<>();
        for (int i = 0; i < 10001; i++) {
            list.add(new ArrayList<>());
        }

        // 출발지에서 최소 거리 기록
        dist = new int[d+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()); // 시작 위치
            int end = Integer.parseInt(st.nextToken()); // 도착 위치
            int dist = Integer.parseInt(st.nextToken()); // 지름길의 거리

            // 도착 위치는 고속도로의 길이를 넘으면 안됨, 역주행 불가
            if (end > d) continue;
            // 지름길이 모두 최단 거리는 아님
            // 110 -> 140, 90은 지름길이 더 멀음
            // 지름길인 경우에만 list 추가
            if (end - start > dist) {
                list.get(start).add(new pos(end, dist));
            }
        }

        dijkstra(0);

        bw.append(dist[d] + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dijkstra(int end) {
        PriorityQueue<pos> pq = new PriorityQueue<>();
        pq.offer(new pos(end, 0));
        checked = new boolean[d+1];
        dist[end] = 0;

        while (!pq.isEmpty()) {
            pos now = pq.poll();
            end = now.end;
            checked[end] = true;

            if (end == d) break; // 도착

            // 거리 1씩 증가
            if (dist[end+1] > now.dist+1) {
                dist[end+1] = now.dist+1;
                pq.offer(new pos(end+1, dist[end+1]));
            }

            // 해당 지점으로 가는 지름길이 있다면
            for (pos next : list.get(end)) {
                // 가중치가 더 작다면 갱신
                if (!checked[next.end] &&  dist[next.end] > dist[end] + next.dist) {
                    dist[next.end] = dist[end] + next.dist;
                    pq.offer(new pos(next.end, dist[next.end]));
                }
            }
        }
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 최단경로
• 특정한 최단 경로
• 특정 거리의 도시 찾기