[SDS 알고리즘 특강 복습 - 오답] 13308 주유소 (다익스트라+DP)

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

 

DP를 쓸 생각을 못함..

진짜 1시간30분~2시간 정도 고민해서 겨우 구현 아이디어 떠올렸는데 반례가 있네 ㅠㅠ

1번 노드에서 다익스트라 쫙 돌려서 임의의 K번 노드까지 가는 비용 구한 다음에

K번노드에서 마지막 노드까지 가는 비용 구해서

최단거리 구하는 방식으로 했음.

(K번 노드까지 "손해를 보면서(위험을 감수하고)" 도달한 다음 싼 값에 기름 쫙 충전에서 도착지까지 가는 방법)

 

그런데 이렇게하면 위험을 감수하고 도달하는 노드가 하나일 경우까지만 작동함..!

1번노드에서 2번노드가서 기름채우고

2번노드에서 1번노드 돌아와서 3번노드가서 기름 다시 채우고

3번노드에서 1번노드간 다음에 4번노드로 가는 케이스에는 틀리는 코드임..!!

 

이 경우 DP를 써야함 ㅠ.ㅠ

아직 DP적 사고가 많이 부족해서 아예 생각을 못했다.

 

---

그리고 DP가 쓰인 코드를 봐도 이해가 안됐는데..

DP[P][minOil] <- minOil의 최소단위오일값일 때의 P노드까지의 비용이라

요 값을 계속 업데이트해주면서 pq에 넣으면 특정 노드의 모든 최소단위오일값에 대해 처리가 되면서 기존에 방문하면서 동일한 최소단위오일값은 반복하지 않게 된다. (와..)

 

그리고 pq이므로 꺼낸 노드가 N번째일 때는 앞의 노드들의 비용이 최적화가 된 것임..!!! (와2...)

---

제일 처음에

dist - 총비용저렴버전, dist - 오일값저렴버전 이렇게 2개 만들어서
항상 2개에 대해서 계산하는 알고리즘 구상했었는데

그냥 dp를 DP[P][minOil] <- minOil의 최소단위오일값일 때의 P노드까지의 비용이라

이렇게 구성하면 해결 됐었다.

버전이 여러개 필요할 때 dp를 쓰는 것을 고려해보자..!!

내일이 시험인데 이거 아주 큰일이다..

떨어지더라도 최선을 다해서 할 때 까지 해보자

화이팅!

 

<내 틀린 코드(부분 정답)>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int V, E;
    static long INF = Long.MAX_VALUE;
    static int[] oil;
    static ArrayList<ArrayList<int[]>> edge;
    static PriorityQueue<long[]> pq;
    static long[][] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        oil = new int[V + 1];
        edge = new ArrayList<>();
        pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1[1], o2[1]));
        st = new StringTokenizer(br.readLine());
        dist = new long[V + 1][V + 1];

        for (int i = 0; i <= V; i++) {
            edge.add(new ArrayList<>());
            Arrays.fill(dist[i], INF);
            if (i != 0) oil[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edge.get(a).add(new int[]{b, c, oil[b]});
            edge.get(b).add(new int[]{a, c, oil[a]});
        }

        dist[1][1] = 0;
        pq.add(new long[]{1, dist[1][1], oil[1]});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            int node = (int) cur[0];
            long cost = cur[1];
            int oill = (int) cur[2];

            for (int[] e : edge.get(node)) {
                int next = e[0];
                long w = e[1];
                int nextOil = e[2];

                if (dist[1][next] > cost + w * oill) {
                    dist[1][next] = cost + w * oill;
                    pq.add(new long[]{next, dist[1][next], Math.min(oill, nextOil)});
                }
            }
        }

        long min = INF;
        for (int k = 2; k < V; k++) {
            dist[k][k] = 0;
            pq.add(new long[]{k, dist[k][k], oil[k]});

            while (!pq.isEmpty()) {
                long[] cur = pq.poll();
                int node = (int) cur[0];
                long cost = cur[1];
                int oill = (int) cur[2];

                for (int[] e : edge.get(node)) {
                    int next = e[0];
                    long w = e[1];
                    int nextOil = e[2];

                    if (dist[k][next] > cost + w * oill) {
                        dist[k][next] = cost + w * oill;
                        pq.add(new long[]{next, dist[k][next], Math.min(oill, nextOil)});
                    }
                }
            }
            min = Math.min(dist[1][k] + dist[k][V], min);
        }
        System.out.println(min);
    }
}

 

<정답 코드>

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

public class Main {

    static int N, M, c[];
    static ArrayList<ArrayList<int[]>> e;
    static PriorityQueue<long[]> pq;
    static long d[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        e = new ArrayList<ArrayList<int[]>>();
        st = new StringTokenizer(br.readLine());
        c = new int[N+1];
        e.add(new ArrayList<int[]>());
        for (int i=1; i<=N; i++) {
            e.add(new ArrayList<int[]>());
            c[i] = Integer.parseInt(st.nextToken());
        }
        int a, b, w;
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            e.get(a).add(new int[] {b, w});
            e.get(b).add(new int[] {a, w});
        }

        d = new long[N+1][2501];
        for (int i=1; i<=N; i++) {
            for (int j=0; j<=2500; j++) {
                d[i][j] = Long.MAX_VALUE;
            }
        }
        pq = new PriorityQueue<long[]>((o1, o2) -> {
            return (int)(o1[0]-o2[0]);
        });
        pq.add(new long[] {0, 1, c[1]});
        long ans = 0, total, temp[];
        int node, cost, to, minCost;
        while (!pq.isEmpty()) {
            temp = pq.poll();
            total = temp[0];
            node = (int)temp[1];
            minCost = (int)temp[2];
            if (node == N) {
                ans = total;
                break;
            }
            for (int i=0; i<e.get(node).size(); i++) {
                to = e.get(node).get(i)[0];
                cost = e.get(node).get(i)[1];
                if (d[to][minCost] > total+(cost*minCost)) {
                    d[to][minCost] = total+(cost*minCost);
                    pq.add(new long[] {d[to][minCost], to, Math.min(minCost, c[to])});
                }
            }
        }
        System.out.println(ans);
    }
}