백준(BOJ) 1162: 도로포장 풀어야 함

나는 처음에 다익스트라를 이용하고 거기서 얻어진 최소경로가 있으면 그 최소경로를 구성하는 부분 경로의 값중에서 큰 것부터 차례로 k개 제거하려고 생각했었다. 하지만 이건 틀렸다. 그건 어디까지나 다익스트라를 통한 최단경로이지 그 경로 값을 완전히 0으로 바꾸어 버리면 더이상은 그 경로가 최단경로가 될수 있다는 보장이 없어져 버리는 것이기 때문이다. 이것에 대한 해결책으로 dp가 등장하게 된다.

아래는 열심히 한 잘못된 풀이

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

public class Testing3 {

    static class Point {
        int cur;
        int cost;

        public Point(int cur, int cost) {
            this.cur = cur;
            this.cost = cost;
        }

        int getCur() {
            return cur;
        }

        int getCost() {
            return cost;
        }
        int getReverseCost(){
            return -cost;
        }
    }

    static final int INF = 987654321;

    public static void solution(List<List<Point>> graph, int n, int k) {
        //다익스트라의 변형. 시작점에서 목표지점까지가는 최단경로를 기록하여야 함. 기록한것을 내림차순으로 정리하여 앞에서 부터 k개
        //제거하면 됨.
        int[] path = new int[n + 1];
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparing(Point::getCost));
        pq.add(new Point(1, 0));
        boolean[] visited = new boolean[n + 1];
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        while (!pq.isEmpty()) {
            Point cur = pq.poll();
            if (!visited[cur.cur]) {
                visited[cur.cur] = true;
                for (var nextV : graph.get(cur.cur)) {
                    if (dist[cur.cur] != INF && dist[cur.cur] + nextV.cost < dist[nextV.cur]) {
                        dist[nextV.cur] = dist[cur.cur] + nextV.cost;
                        path[nextV.cur] = cur.cur;
                        pq.add(new Point(nextV.cur, dist[nextV.cur]));
                    }
                }
            }
        }

        //다익스트라 끝난후 목표점에서 이전 방문했던 점을 거꾸로 거슬러 올라가면서 구간의 거리를 우선순위 큐에 넣는다. 큐의 기준은 바꾸어준다.
        //마지막으로 큐에서 k개 빼낸다. 그러면 남아있는 데이터의 합이 정답이다.
        //OptionalInt result=graph.get(arr[1]).stream().filter(ss->ss.getCur()==특정정점).mapToInt(Point::getCost).findFirst();
        //System.out.println(result.getAsInt());
        pq=new PriorityQueue<>(Comparator.comparing(Point::getCost));
        int vertex=n;
        while(true){
            int former=path[vertex];
//            System.out.println("지금정점:"+vertex+", 이전정점:"+former);
            int reuslt=graph.get(vertex).stream().filter(v->v.getCur()==former).mapToInt(Point::getCost).findFirst().getAsInt();
            pq.add(new Point(former, -reuslt));
            vertex=former;
            if(former==1)
                break;
        }
        pq.stream().mapToInt(Point::getCur).forEach(System.out::println);
        for(int i=0;i<k;i++)
            pq.poll();
        int answer=0;
        while(!pq.isEmpty())
            answer+=(-pq.poll().getCost());
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        List<List<Point>> graph = new LinkedList<>();
        for (int i = 0; i <= n; i++)
            graph.add(new LinkedList<>());
        for (int i = 0; i < m; i++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            graph.get(arr[0]).add(new Point(arr[1], arr[2]));
            graph.get(arr[1]).add(new Point(arr[0], arr[2]));
        }
        solution(graph, n, k);

    }
}