[SDS 알고리즘 특강 복습] 5719 거의 최단 경로 (다익스트라)

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

 

다익스트라 응용 문제.

역추적 아이디어가 필요.

 

내가 실수한 부분은 여러가지임

1. arraylist remove되는지 안되는지를 몰랐는데 -> 해보니까 안됨.
    그래서 remove확인 하는법 확인하려고 답지를 봤는데 답지에서도 remove안씀. flag를 씀.. 
    반성해야함 remove안되면 다른 방법 모색했어야했는데 무조건 remove된다고 생각했음.
    실전스럽지 못했음.

2. 방문한 최단경로를 [V][V]에 저장했는데 이렇게하니까 메모리초과뜸.
    [E]에 저장하는게 25배 메모리 덜 소요.

3. DP적 사고도 해줘야함. 이미 방문한 노드에 대해서는 쓸데없는 계산하지 않도록..!!

 

얻어 갈 것이 굉장히 많은 문제로 보임!!

복습해서 다 얻어가자. 유사한 문제가 출제될 것도 같으니 확실히 가져가자!!

 

<내 정답 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    static int V, E, S, D, INF = 987654321;
    static ArrayList<ArrayList<int[]>> edge;
    static ArrayList<ArrayList<int[]>> reverseEdge;
    static int[] used;
    static PriorityQueue<int[]> pq;
    static int[] dist;
    static Queue<Integer> q;

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

        while(true) {
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            if(V==0 && E==0) break;
            st = new StringTokenizer(br.readLine());
            S = Integer.parseInt(st.nextToken());
            D = Integer.parseInt(st.nextToken());
            edge = new ArrayList<>();
            reverseEdge = new ArrayList<>();
            used = new int[E];
            dist = new int[V];
            pq = new PriorityQueue<>((o1, o2) -> {
                return o1[1] - o2[1];
            });
            q = new LinkedList<>();
            for (int i = 0; i < V; i++) {
                dist[i] = INF;
                edge.add(new ArrayList<>());
                reverseEdge.add(new ArrayList<>());
            }
            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, i});
                reverseEdge.get(b).add(new int[]{a, c, i});
            }
            dist[S] = 0;
            pq.add(new int[]{S, 0});
            int[] cur;
            int node, cost, next, w, ri;
            while (!pq.isEmpty()) {
                cur = pq.poll(); // 노드와 비용 cur에 저장
                node = cur[0];
                cost = cur[1];
                // 뽑은 노드에 대해 연결된 노드들까지의 비용 재계산 및 pq에 푸시
                for (int i = 0; i < edge.get(node).size(); i++) {
                    next = edge.get(node).get(i)[0];
                    w = edge.get(node).get(i)[1];
                    if (dist[next] > dist[node] + w) {
                        dist[next] = dist[node] + w;
                        pq.add(new int[]{next, dist[next]});
                    }
                }
            }

            /*
            D부터 시작해서 인접한 노드 poll
            [인접한 노드까지 비용] + [인접노드 -> 현재노드 간선 비용] == [현재노드까지의 비용 이면]
                해당 간선 삭제, 인접노드를 푸시
            by BFS
            */
            q.add(D);
            int curr;
            while (!q.isEmpty()) {
                curr = q.poll();
                for (int i = 0; i < reverseEdge.get(curr).size(); i++) {
                    next = reverseEdge.get(curr).get(i)[0];
                    w = reverseEdge.get(curr).get(i)[1];
                    ri = reverseEdge.get(curr).get(i)[2];
                    if(used[ri] == 1) continue;
                    if (dist[next] + w == dist[curr]) {
                        //                    edge.get(next).remove(new int[]{node, w});
                        used[ri] = 1;
                        q.add(next);
                    }
                }
            }

            /*
            간선 제거후 재 다익스트라.
             */
            for (int i = 0; i < V; i++) {
                dist[i] = INF;
            }
            dist[S] = 0;
            pq.add(new int[]{S, 0});
            while (!pq.isEmpty()) {
                cur = pq.poll(); // 노드와 비용 cur에 저장
                node = cur[0];
                cost = cur[1];
                // 뽑은 노드에 대해 연결된 노드들까지의 비용 재계산 및 pq에 푸시
                for (int i = 0; i < edge.get(node).size(); i++) {
                    next = edge.get(node).get(i)[0];
                    w = edge.get(node).get(i)[1];
                    ri = edge.get(node).get(i)[2];
                    if (dist[next] > dist[node] + w && used[ri] == 0) {
                        dist[next] = dist[node] + w;
                        pq.add(new int[]{next, dist[next]});
                    }
                }
            }
            sb.append(dist[D] == INF ? -1 + "\n" : dist[D] + "\n");
        }
        System.out.println(sb.toString());
    }
}