[백준 1948] 임계경로 (JAVA)

문제

월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.

이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.

어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라.

출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

입력

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다.

그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.

모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

출력

첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하여라.

예제 입력 1 

7
9
1 2 4
1 3 2
1 4 3
2 6 3
2 7 5
3 5 1
4 6 4
5 6 2
6 7 5
1 7

예제 출력 1 

12
5

---

어렵다..

 

출발하는 도시와 도착하는 도시가 지정되기 때문에 일반적인 위상 정렬이 아니라, 목적에 따라 queue 에 넣는 노드를 다르게 해주어야 한다.

 

1분도 쉬지 않고 달려야 하는 도로의 개수를 구하는 데에는 역방향 그래프에서 위상정렬을 수행한다는 특별한 아이디어가 필요하다.

 

이를 위해서 정방향 그래프 뿐만이 아니라 역방향 그래프를 따로 선언해주어서 만들어주어야 한다.

그리고 정방향 그래프에서 시작 도시를 출발점으로 지정하여 위상정렬을 수행하는데,

중요한 것은 임계 경로 값을 도로별로 저장해주어야 한다는 것이다.

 

임계 경로 배열 path 에대하여 path[i] 는 i 번째 도로에 도달하는 데에 걸리는 최대 시간을 말한다.

 

정방향 그래프에서 위상정렬을 수행하여 임계 경로 배열을 초기화해주면 이제 역방향 그래프에서 위상정렬을 수행한다.

 

이때는 도착 도시가 시작점이 된다. 

 

  위상정렬을 수행한다. 예를 들어서 A -> B 라는 경로를 탐색하게 된다면,

현재 임계 경로값인 path[A] 와 path[B]+ edge 를 비교한다. 만약 두 값이 동일하다면 A 에서 B 로 도달하는 것이 1분도 쉬지 않아야 하는 임계 경로라는 것이다. 이러한 경우를 카운팅해준다.

 

  중요한 것은 queue 에 새로운 노드를 넣을 때, 중복해서 넣을 수 있는 가능성이 있다는 것이다. 이를 방지하기 위해 별도의 방문 배열을 선언한 다음에 중복한 노드가 Queue 에 들어가지 않도록 방지해주면 된다.

 

  그리고 path[도착도시] 와 cnt를 차례대로 출력하면 된다. 쉽지 않네!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken()); // node 개수
        stk = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(stk.nextToken()); // edge 개수

        ArrayList<ArrayList<Node>> graph = new ArrayList<>(); // 정방향 그래프
        ArrayList<ArrayList<Node>> reverse_graph = new ArrayList<>(); // 역방향 그래프

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Node>());
            reverse_graph.add(new ArrayList<Node>());
        }
        int[] indegree = new int[n + 1];
        int[] path = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int e = Integer.parseInt(stk.nextToken());
            graph.get(a).add(new Node(b, e));
            indegree[b]++;
            reverse_graph.get(b).add(new Node(a, e));
        }
        stk = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(stk.nextToken());
        int end = Integer.parseInt(stk.nextToken());
        //// 입력 끝

        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        while (!q.isEmpty()) {
            int now = q.poll();
            for (Node cur : graph.get(now)) {
                // 연결 성분 탐색
                indegree[cur.toNode]--;
                path[cur.toNode] = Math.max(path[cur.toNode], path[now] + cur.e);
                if (indegree[cur.toNode] == 0)
                    q.offer(cur.toNode);
            }
        }
        // 역위상정렬
        q.offer(end);
        int cnt = 0;
        boolean[] visited = new boolean[n + 1];
        visited[end] = true;
        while (!q.isEmpty()) {
            int now = q.poll();
            for (Node cur : reverse_graph.get(now)) {
                if (path[now] == path[cur.toNode] + cur.e) {
                    // 임계 경로이면
                    cnt++; // 도로 개수 카운팅
                    if (!visited[cur.toNode]) {
                        // 아직 미방문인 노드라면
                        q.offer(cur.toNode);
                        visited[cur.toNode] = true;
                    }
                }
            }
        }
        System.out.println(path[end]);
        System.out.println(cnt);
    }

    static class Node {
        int toNode;
        int e;

        public Node(int toNode, int e) {
            this.toNode = toNode;
            this.e = e;
        }
    }
}