문제 설명

문제 분석

<aside> 💡 노드를 큐에 삽입할 때 주의할 점

1분도 쉬지 않고 달려야 하는 도로로 이어진 노드와 연결된 다른 도로만이 1분도 쉬지 않고 달려야 하는 도로의 후보가 될 수 있으므로 이 매커니즘을 바탕으로 노드를 큐에 삽입해야 한다. 또한 중복으로 도로를 카운트하지 않기 위해 이미 방문한 노드는 큐에 넣지 않아야 한다.

</aside>

슈도코드

구현

public class 임계경로구하기_1948 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine()); //도시의 개수
        int m = Integer.parseInt(reader.readLine()); //도로의 개수
        ArrayList<ArrayList<Node>> cities = new ArrayList<>();
        ArrayList<ArrayList<Node>> reverseCities = new ArrayList<>();

        //각 도시 노드들 초기화 (반대도)
        for (int i = 0; i <= n; i++) {
            cities.add(new ArrayList<>());
            reverseCities.add(new ArrayList<>());
        }

        int[] indegree = new int[n+1]; //진입 차수 배열

        //도로 연결
        StringTokenizer tokenizer;
        for (int i = 0; i < m; i++) {
            //출발 도시 번호, 도착 도시 번호, 소요 시간
            tokenizer = new StringTokenizer(reader.readLine());
            int start = Integer.parseInt(tokenizer.nextToken());
            int end = Integer.parseInt(tokenizer.nextToken());
            int time = Integer.parseInt(tokenizer.nextToken());

            cities.get(start).add(new Node(end, time));
            reverseCities.get(end).add(new Node(start, time));
            indegree[end]++;
        }

        tokenizer = new StringTokenizer(reader.readLine());
        int startCity = Integer.parseInt(tokenizer.nextToken());
        int endCity = Integer.parseInt(tokenizer.nextToken());

        //위상 정렬
        Queue<Integer> q = new LinkedList<>();
        q.add(startCity);
        int[] result = new int[n + 1];
        while(!q.isEmpty()) {
            int curCity = q.poll();
            for (Node next : cities.get(curCity)) {
                indegree[next.target]--;
                result[next.target] = Math.max(result[next.target], result[curCity] + next.time);

                if (indegree[next.target] == 0) {
                    q.add(next.target);
                }
            }
        }
        
        // 반대 위상 정렬
        int resultCnt = 0;
        boolean[] visited = new boolean[n+1];
        q = new LinkedList<>();
        q.add(endCity);
        visited[endCity] = true;
        while(!q.isEmpty()) {
            int curNode = q.poll();
            for (Node next : reverseCities.get(curNode)) {
                // 1분도 쉬지 않는 도로
                if(result[next.target] + next.time == result[curNode]) {
                    resultCnt++;
                    // 중복 카운트 방지하지 위해 방문한 노드 제외
                    if(!visited[next.target]) {
                        visited[next.target] = true;
                        q.add(next.target);
                    }
                }
            }
        }

        System.out.println(result[endCity]);
        System.out.println(resultCnt);
    }
}

class Node {
    int target;
    int time;

    public Node(int target, int time) {
        this.target = target;
        this.time = time;
    }
}