백준 1948 (임계경로) - java

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

1948번: 임계경로

문제 : 

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

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

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

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

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

유형 : 위상정렬 , BFS

접근 방식

• 마지막에 도착하는 사람의 시간 -> 위상 정렬을 통해 목적지에 도착하는 가장 마지막 시간을 구한다.
• 최장 시간 경로의 도로의 수 -> BFS 사용 
  • 최장 시간이 걸리는 경로의 개수가 복수개일 수 있다.
    • ArrayList<Integer>[] past 사용
    • 위상 정렬을 수행 하는 와중에 더 긴 시간으로 갱신된 경우 -> clear() + add()
    • 값이 동일한 경로가 추가된 경우 -> add()

전체 코드

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

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

    static ArrayList<Node>[] graph;
    static int[] count;

    static ArrayList<Integer>[] past;

    static int start = 0;
    static int end = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());

        count = new int[n + 1];
        graph = new ArrayList[n + 1];
        past = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            past[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());

            graph[x].add(new Node(y, c));
            count[y] += 1;
        }

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

        search();
        br.close();
    }

    static void search() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(start, 0));
        int[] time = new int[n + 1];

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

            for (Node next : graph[cur.v]) {
                count[next.v] -= 1;

                if (time[next.v] < time[cur.v] + next.c) {
                    time[next.v] = time[cur.v] + next.c;

                    past[next.v].clear();
                    past[next.v].add(cur.v);
                } else if (time[next.v] == time[cur.v] + next.c) {
                    past[next.v].add(cur.v);
                }

                if (count[next.v] == 0) {
                    q.add(new Node(next.v, time[next.v]));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(time[end] + "\n");
        sb.append(count() + "\n");

        System.out.print(sb);
    }

    static int count() {
        int result = 0;
        boolean[][] v = new boolean[n + 1][n+1];
        Queue<Integer> q = new LinkedList<>();
        q.add(end);

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

            if (cur == 0)
                continue;

            for (int next : past[cur]) {
                if(!v[cur][next]) {
                    v[cur][next] = true;
                    v[next][cur] = true;
                    result += 1;
                    q.add(next);
                }
            }
        }

        return result;
    }
}

class Node {
    int v;
    int c;

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