[BOJ] 백준 [5719] 거의 최단 경로 JAVA

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

5719번: 거의 최단 경로

문제

풀이

쉽게 풀 수 있을줄 알았다 .. 최단 경로 찾아서 없애주고 , 처음 구한 최단경로보다 높은 값 나올때까지

다익스트라 다시 쓰면 되는줄 ..하지만 실패하고 반례를 살펴보니 다른 조건이 추가되어야 했다.

예를들어 , 0에서 출발하여 2로 도착하는 예시에서

최단 경로가 될 수 있는 경우의 수는 2가지이다. (0->3->2 , 0->3->1->2)

만약 0->3->2 경로를 지운다고 하면 남은 경로인 0->1->2 가 정답이 아닌 '경로는 없음'이 정답이란 것.

즉 , 다른 최단거리 경로인 0->3->1->2 또한 마찬가지로 지워줘야 한다.

 

다익스트라 경로 설정부분에서

1.경로가 갱신될 때 , 이전 경로가 싹 다 바뀌기 때문에 pathList를 초기화 하고 다시 담거나

2.같은 최단거리의 다른 경로가 있으면 해당 경로만 담도록하여 경로배열을 모두 채운다.

 

그런 다음 큐를 이용하여 순차적으로 도착지점에서부터 시작해서 역추적 + 경로제거 를 동시에 시행.

이게 끝나야 다익스트라를 한번 더 돌렸을 때 원하는 답을 구할 수 있음

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main{
 
    static int N,E;
    static ArrayList<Node>[] list;
    static int[] distance;
    static ArrayList<Integer>[] pathList;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        while(!(input=br.readLine()).equals("0 0")){
            int[] e = Arrays.stream(input.split(" ")).mapToInt(Integer::parseInt).toArray();
            int[] point = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            N=e[0]; E=e[1]; // 노드 , 엣지 개수 초기화
            list = new ArrayList[N];
            pathList = new ArrayList[N]; // 경로 역추적을 하기위한 배열
            distance = new int[N];
 
            for(int i=0;i<N;i++) {
                list[i] = new ArrayList<>();
                pathList[i] = new ArrayList<>();
            }
            for(int i=0;i<E;i++){
                e = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                list[e[0]].add(new Node(e[1],e[2]));
            }
 
            int len = findShortestPath(point[0], point[1]);
            removePath(point[1]);
 
            int ret = findShortestPath(point[0], point[1]);
            if(ret==Integer.MAX_VALUE || len==Integer.MAX_VALUE)
                System.out.println(-1);
            else
                System.out.println(ret);
        }
    }
    static int findShortestPath(int start,int end){
;
        Arrays.fill(distance,Integer.MAX_VALUE);
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start,0));
        distance[start] = 0;
        while(!q.isEmpty()){
            Node cur = q.poll();
 
            if(distance[cur.node] < cur.weight) continue;
 
            for (Node next : list[cur.node]) {
                if(distance[next.node] > distance[cur.node]+next.weight) {
                    distance[next.node] = distance[cur.node] + next.weight;
                    q.add(new Node(next.node,distance[next.node]));
                    pathList[next.node].clear();
                    pathList[next.node].add(cur.node);
                }else if(distance[next.node] == distance[cur.node]+next.weight) {
                    pathList[next.node].add(cur.node);
                }
            }
        }
        return distance[end];
    }
    static void removePath(int end){
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(end);
        while(!queue.isEmpty()){
            int poll = queue.poll();
            pathList[poll].forEach(e->list[e].stream().filter(x->x.node==poll).findAny().ifPresent(x->{
                list[e].remove(x);
                queue.add(e);
            }));
        }
    }
    static class Node implements Comparable<Node>{
        int node;
        int weight;
 
        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight;
        }
    }
}