백준 5719 (거의 최단 경로) - java

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

5719번: 거의 최단 경로

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

유형 : 다익스트라 + 경로 역추적 + BFS

접근

• 우선 최단 경로를 구해야 하며 해당 경로를 이루는 간선의 정보를 파악해야 한다. -> 다익스트라
• 각 정점에 대하여 ArrayList<Integer>[] past 를 통해 최단 경로의 정보를 저장한다.
• BFS를 통해 최단 경로에 포함된 간선들을 지워준다.
• 다익스트라 다시 한번 수행 -> 거의 최단 경로

다익스트라의 가장 큰 특징 

• 다익스트라 알고리즘에는 굉장히 중요한 특징이 있다. 
• 해당 경로가 최단 경로라면 경로를 이루는 간선들(일종의 작은 경로)로 최단 경로이다 !!!!

동작 과정 

1. 다익스트라 -> 최단 경로 찾기
2. BFS (경로 역추적) -> 최단 경로 간선 제거
3. 다익스트라 -> 거의 최단 경로

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n = 0;
    static int m = 0;

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

        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            if (n == 0 && m == 0)
                break;

            st = new StringTokenizer(br.readLine(), " ");

            int start = Integer.parseInt(st.nextToken());
            int last = Integer.parseInt(st.nextToken());


            ArrayList<Edge>[] graph = new ArrayList[n];
            int[][] allDis = new int[n + 1][n + 1];

            for (int i = 0; i <= n - 1; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 1; i <= m; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                allDis[x][y] = c;
                graph[x].add(new Edge(y, c));
            }
            searchMax(graph, start, last, allDis);
            int max = findSecond(graph,start,last,allDis);
            sb.append(max+"\n");
        }
        System.out.print(sb);
    }
    static int searchMax(ArrayList<Edge>[] graph,int start,int end,int[][] allDis)
    {
        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        boolean[] visit = new boolean[n];
        int[] dis = new int[n];
        ArrayList<Integer>[] list = new ArrayList[n];

        for(int i=0;i<n;i++) {
            list[i] = new ArrayList<>();
            dis[i] = Integer.MAX_VALUE;
        }

        dis[start] = 0;
        pq.add(new Edge(start,0));

        while(!pq.isEmpty())
        {
            Edge cur = pq.poll();

            if(visit[cur.v])
                continue;

            visit[cur.v] = true;

            for(Edge next : graph[cur.v])
            {
                if(dis[cur.v] + next.c < dis[next.v])
                {
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Edge(next.v , dis[next.v]));
                    list[next.v].clear();
                    list[next.v].add(cur.v);
                }

                else if(dis[cur.v] + next.c == dis[next.v]){
                    list[next.v].add(cur.v);
                }
            }
        }

        if(dis[end] == Integer.MAX_VALUE )
            dis[end] = -1;

        Queue<Integer> q = new LinkedList<>();
        boolean[] v = new boolean[n];
        q.add(end);
        v[end] = true;

        while(!q.isEmpty()){
            int cur = q.poll();


            for(int next : list[cur]){
                allDis[next][cur] = Integer.MAX_VALUE;

                if(!v[next]) {
                    q.add(next);
                    v[next] = true;
                }
            }
        }


        return dis[end];
    }

    static int findSecond(ArrayList<Edge>[] graph,int start,int end,int[][] allDis){
        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        boolean[] visit = new boolean[n];
        int[] dis = new int[n];


        for(int i=0;i<n;i++) {
            dis[i] = Integer.MAX_VALUE;
        }

        dis[start] = 0;
        pq.add(new Edge(start,0));

        while(!pq.isEmpty())
        {
            Edge cur = pq.poll();

            if(visit[cur.v])
                continue;

            visit[cur.v] = true;

            for(Edge next : graph[cur.v])
            {
                if(allDis[cur.v][next.v] == Integer.MAX_VALUE)
                    continue;

                if(dis[cur.v] + next.c < dis[next.v])
                {
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Edge(next.v , dis[next.v]));
                }

            }
        }

        if(dis[end] == Integer.MAX_VALUE )
            dis[end] = -1;

        return dis[end];
    }
}
class Edge
{
    int v;
    int c;

    Edge(int v,int c)
    {
        this.v = v;
        this.c = c;
    }
}