[백준] 5719번 : 거의 최단 경로

5719번: 거의 최단 경로

---

[다익스트라 알고리즘 + DFS 또는 BFS]

이 문제를 풀기 위해선 다음과 같은 작업을 해야한다.

 

1. start -> end의 최단 경로 구하기

2. 최단 경로 제거하기

3. 다시 최단경로 구하기

 

1, 3번 같은 경우는 그냥 다익스트라를 이용하면 되나, 2번이 조금 까다로울 수 있다. 방법은 DFS나 BFS를 이용해 최단 경로를 제거하는 방법인데, 우선 최단 경로를 추가적인 인접 리스트 같은 곳에 저장해두도록 한다.

 

            //다익스트라 메소드의 일부
            for(int a=0; a<list[current].size(); a++){
                Edge nextEdge = list[current].get(a);

                int next = nextEdge.tg;
                int nextD = nextEdge.d + d;

                if (distance[next] > nextD) {
                    shortest[next].clear();
                    shortest[next].add(new Edge(current, a));

                    distance[next] = nextD;
                    Q.add(new Edge(next, nextD));
                }
                else if (distance[next] == nextD)
                    shortest[next].add(new Edge(current, a)); //Edge의 2번째 멤버변수로 list[current]의 몇 번째 인덱스인지 저장

            }

최단 경로들을 shortes[]라는 ArrayList에 저장하는 코드이다. 최단 경로가 2개 이상일 수 있음에 주의한다.

 

이제 DFS나 BFS를 가지고 최단 경로의 도착점(end)부터 출발점(start)로의 탐험을 시작하며 각 경로를 제거한다. 

//list의 입장에서 next는 current이고, 
//shortest의 입장에서 current는 next이다.
//즉 list[current] == shortest[next], 같은 정점에 대한 리스트이다.
    static boolean[] visit;
    static void DFS(int current, int start){

        if(current == start || visit[current]) return;
        visit[current] = true;

        for(Edge edge:shortest[current]){
            int next = edge.tg;
            int idx = edge.d;

            list[next].set(idx, new Edge(0, INF));

            DFS(next, start);
        }
    }

인접 리스트에 저장된 최단 경로에 포함되는 경로의  가중치를 INF로 변경하는 코드이다. 제거한다고 말했지만 사실 제거하면 안되는 것이 ArrayList에서 인덱스로 지우도록 해놨기 때문에 지우면 인덱스에 변동이 생겨 에러가 발생한다. 따라서 값을 변경하는 것으로 대체하였다.

 

그리고 visit를 사용하지 않으면 시간 초과를 마주하게 된다.

 

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int tg, d;
        public Edge(int t, int dist){
            tg=t; d=dist;
        }
        @Override
        public int compareTo(Edge o) {
            return d - o.d;
        }
    }

    static final int INF = 100000000, N = 500;
    static ArrayList<Edge>[] list = new ArrayList[N], shortest = new ArrayList[N];
    static int[] distance;

    static void Dijkstra(int start){
        PriorityQueue<Edge> Q = new PriorityQueue<>();

        distance[start] = 0;
        Q.add(new Edge(start, 0));

        while(!Q.isEmpty()){
            Edge edge = Q.poll();
            int current = edge.tg;
            int d = edge.d;

            if(distance[current] < d) continue;

            for(int a=0; a<list[current].size(); a++){
                Edge nextEdge = list[current].get(a);

                int next = nextEdge.tg;
                int nextD = nextEdge.d + d;

                if (distance[next] > nextD) {
                    shortest[next].clear();
                    shortest[next].add(new Edge(current, a));

                    distance[next] = nextD;
                    Q.add(new Edge(next, nextD));
                }
                else if (distance[next] == nextD)
                    shortest[next].add(new Edge(current, a)); //Edge의 2번째 멤버변수로 list[current]의 몇 번째 인덱스인지 저장

            }
        }
    }
    static boolean[] visit;
    static void DFS(int current, int start){

        if(current == start || visit[current]) return;
        visit[current] = true;

        for(Edge edge:shortest[current]){
            int next = edge.tg;
            int idx = edge.d;

            list[next].set(idx, new Edge(0, INF));

            DFS(next, start);
        }
    }

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

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            if(v == 0 && e == 0) break;

            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            distance = new int[v];
            visit = new boolean[v];
            IntStream.range(0,v).forEach(i->{
                distance[i]=INF;
                list[i] = new ArrayList<>();
                shortest[i] = new ArrayList<>();
            });

            for(int i=0; i<e; i++){
                st = new StringTokenizer(br.readLine());

                int h = Integer.parseInt(st.nextToken());
                int tg = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                list[h].add(new Edge(tg, d));
            }

            Dijkstra(start);

            DFS(end, start);

            IntStream.range(0,v).forEach(i->distance[i]=INF);

            Dijkstra(start);
            System.out.println(distance[end] == INF? -1 : distance[end]);
        }
    }
}