[Boj_20160] 야쿠르트 아줌마 야쿠르트 주세요

📎 문제 링크

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

 

▸ 문제

야쿠르트를 외치며 잠에서 깼다. 오늘은 야쿠르트로 하루를 시작하려고 한다.

야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 각 지점에서 야쿠르트 아줌마보다 같거나 더 일찍 도착한 사람에게 야쿠르트를 팔고 바로 다음 지점으로 출발하신다. 각 지점은 정점 위에 있고 지정된 차례에만 야쿠르트를 판매한다. 야쿠르트를 파는 데 지연되는 시간은 없으며, 오직 이동 시에만 해당 도로의 가중치만큼 시간이 지연된다.

야쿠르트 아줌마는 10개의 지점을 순서대로 방문하며, 10개의 지점 중 첫 번째 지점에서 출발한다. 만약 i번째 지점에서 i+1번째 지점으로 이동 가능한 경로가 없다면 i+2지점으로 이동하신다. i+2로 갈 수 없으면 i+3, i+4...(≤ V)로 이동하신다.

내가 출발하는 시간과 야쿠르트 아줌마가 출발하는 시간은 같다.

내가 출발하는 정점 번호와 야쿠르트 아줌마의 동선을 알려주면 어느 지점으로 가야 야쿠르트를 살 수 있을지 알려줘!!

 

▸ 입력

첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다.

그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ u, v ≤ V) 사이에 가중치가 w(1 ≤ w ≤ 100,000)인 도로가 존재한다는 뜻이다. 정점 사이에는 여러 개의 간선이 존재할 수도 있음에 유의한다.

E+2번째 줄에는 야쿠르트 아줌마가 야쿠르트를 파는 10개 지점의 정점 번호가 주어진다. E+3번째 줄에는 내가 출발하는 정점 번호가 주어진다.

 

▸ 출력

야쿠르트를 살 수 있는 정점이 여러 개라면 그 중 가장 작은 정점 번호를 출력한다.

야쿠르트를 살 수 없다면 -1을 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 3
• 🔔  문제 유형 : 그래프 이론, 최단 경로, 데이크스트라
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

다익스트라 알고리즘을 사용해서 풀 수 있는 문제였다.

 

먼저, 야쿠르트 아줌마가 10개의 지점을 순차적으로 방문할 때 최소 비용을 구한다.

 

이때, 아줌마가 i 번째 지점에서 i+1번째 지점으로 갈 수 없는 경우

즉, 비용이 INF인 경우라면 i+2번째 지점으로 가야 한다.

 

또한, 여기서 나올 수 있는 비용의 최댓값은 10,000(최대 정점의 개수) * 100,000(가중치 최댓값) = 10억이다.

아줌마가 1 ➡ 2 ➡ 1 ➡ 2 ➡ 1로 지점을 방문한다고 가정해 보자

1 ➡ 2로 가는 최소 비용이 최악으로 10억이고, 2 ➡ 1로 가는 비용도 최악으로 10억이라면

아줌마가 지점을 방문할 때마다 누적되는 시간은 아래와 같다.

1 ➡ 2 : 10억

2 ➡ 1 : (이전 10억) + 10억

1 ➡ 2 : (이전 20억) + 10억

2 ➡ 1:  (이전 30억) + 10억

즉, 아줌마가 지점을 방문할 때마다 이전 방문 시간까지 같이 누적해서 저장해 주어야 하기 때문에,

최악의 경우 int형의 범위를 넘게 되므로 long형으로 선언하여 값을 누적해서 더해주어야 한다.

 

다음으로는 내가 출발하는 지점에서 다른 지점까지 가는 최소 비용을 구한다.

 

아줌마가 i 번째 지점에 방문할 수 있고,

내가 아줌마보다 i 번째 지점에 먼저 도착하는 경우에만 정답을 갱신한다.

 

위 풀이대로 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 67096KB
시간 : 700ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int v, e;
    static ArrayList<ArrayList<Pos>> list;
    static PriorityQueue<Pos> pq;
    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;
        }
    }
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken()); // 정점의 개수
        e = Integer.parseInt(st.nextToken()); // 도로의 개수

        list = new ArrayList<>();
        for (int i = 0; i <= v; i++) {
            list.add(new ArrayList<>());
        }

        int u, v, w;
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            list.get(u).add(new Pos(v, w));
            list.get(v).add(new Pos(u, w));
        }

        // 야쿠르트 아줌마가 방문하는 순서
        int[] yogurtNode = new int[10];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 10; i++) {
            yogurtNode[i] = Integer.parseInt(st.nextToken());
        }

        // i번째 지점까지 오는데 소요되는 시간
        long[] yogurtCome = new long[10];
        Arrays.fill(yogurtCome, Long.MAX_VALUE);
        yogurtCome[0] = 0;

        int cur = yogurtNode[0];
        int curIdx = 0;
        for (int i = 1; i < 10; i++) {
            int next = yogurtNode[i];
            // 현재 노드에서 다음 노드까지의 최소거리
            int minDist = dijkstra(cur)[next];

            // 이동 경로가 없다면 그 다음 정점으로
            if (minDist == INF) continue;

            // 이전 방문시간까지 같이 누적
            yogurtCome[i] = minDist + yogurtCome[curIdx];

            cur = next;
            curIdx = i;
        }

        int myStart = Integer.parseInt(br.readLine()); // 내가 출발하는 정점 번호
        int[] myDist = dijkstra(myStart);

        int ans = INF;
        for (int i = 0; i < 10; i++) {
            cur = yogurtNode[i];
            // 아줌마가 i번째 지점으로 올 수 있고,
            // 내가 더 빨리 도착하는 경우
            if (yogurtCome[i] != Long.MAX_VALUE && myDist[cur] <= yogurtCome[i]) {
                ans = Math.min(ans, cur);
            }
        }

        System.out.println(ans == INF ? -1 : ans);
    }

    private static int[] dijkstra(int cur) {
        int[] dist = new int[v+1];
        Arrays.fill(dist, INF);

        pq = new PriorityQueue<>();
        pq.offer(new Pos(cur, 0));
        dist[cur] = 0;

        while (!pq.isEmpty()) {
            Pos now = pq.poll();

            if (now.dist > dist[now.end]) continue;

            for (Pos next : list.get(now.end)) {
                if (dist[next.end] > dist[now.end] + next.dist) {
                    dist[next.end] = dist[now.end] + next.dist;
                    pq.offer(new Pos(next.end, dist[next.end]));
                }
            }
        }

        return dist;
    }
}

 

해결 완료 ! 🔥