[BOJ][Java] 1948번 임계경로

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1948

 

이 문제는 2가지를 구해야 하는 문제이다.

첫 번째는 단순 위상정렬을 통해 도착지점까지 가장 오래 걸리는 경우가 몇인지를 구하면 되기 때문에

비교적 간단하다.

 

두 번째가 이 문제의 핵심인데 가장 먼 거리를 이동하는 루트에 있는 도로의 개수를 구하는 문제이다.

이것은 역방향 인접 그래프를 통해 해결할 수 있다.

 

우선 가장 기본이 되는 정방향 인접그래프를 구현한다.

이때 노드와 노드 사이의 거리도 구해야 하기 때문에 새로운 클래스인

Node 클래스를 만들어 목표 노드와 해당 노드까지의 거리를 나타내고

이를 2차원 리스트에 저장하면 된다.

 

위의 정방향 인접 그래프를 위상정렬 알고리즘을 통해 구하면 위와 같이 

2번 노드부터 7번 노드까지 임계 경로 값을 구할 수 있다.

이제 역방향 인접 그래프를 그려주고

도착지점인 7번 노드부터 거꾸로 올라가면 된다.

이때 해당 도로가 가장 멀리는 걸리는 루트인지 알아보기 위해

만약 현재 노드를 now , 다음 노드를 next라고 하고, 임계값 배열을 sums라고 한다면

sums[now] == ( sums[next] + now에서 next까지의 거리) 인지 확인하고

맞다면 now -> next까지 가는 도로는 가장 오래 걸리는 루트에 포함되는 도로가 된다.

이때 도로를 카운트하는 것의 중복을 방지하기 위해 visited 배열을 선언하고

확인한 후 중복되지 않았을 때만 q에 넣어주면 된다.

 

package boj;

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

public class BOJ1948 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[] sums = new int[n+1]; // 임계값 저장
        List<List<Node>> list = new ArrayList<>(); // 정방향 인접 리스트 저장
        List<List<Node>> reverse = new ArrayList<>(); // 역방향 인접 리스트 저장
        int[] d = new int[n+1]; // 정방향 진입 차수 저장
        Queue<Integer> q = new LinkedList<>(); // 정방향 큐
        Queue<Integer> rQ = new LinkedList<>(); // 역방향 큐
        int count = 0; // 쉬지않고 달려야 하는 도로의 개수
        boolean[] visited = new boolean[n+1]; // 역방향 방문 노드 확인


        for(int i = 0; i <= n; i++){
            list.add(new ArrayList<>());
            reverse.add(new ArrayList<>());
        }

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int dis = Integer.parseInt(st.nextToken());

            d[e]++;  // 정방향 진입 차수 ++
            list.get(s).add(new Node(e,dis)); // 정방향 인접 리스트
            reverse.get(e).add(new Node(s,dis)); // 역방향 인접 리스트
        }

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

        // 최대 길이 구하기
        for(int i = 1; i < d.length; i++){
            if(d[i] == 0) q.add(i);
        }

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

            for(Node next: list.get(now)){
                d[next.end]--;
                sums[next.end] = Math.max(sums[next.end] , sums[now] + next.dis);
                if(d[next.end] == 0) q.add(next.end);
            }
        }

        // 역방향으로 돌면서 쉬지않고 달려야 하는 도로 개수 구하기
        rQ.add(end);

        while(!rQ.isEmpty()){
            int now = rQ.poll();

            for(Node next: reverse.get(now)){
                if(sums[now] == (sums[next.end] + next.dis)){
                    count++;
                    if(!visited[next.end]){
                        visited[next.end] = true;
                        rQ.add(next.end);
                    }
                }

            }
        }

        System.out.println(sums[end]);
        System.out.println(count);

    }
    static class Node {
        int end;
        int dis;

        public Node(int end, int dis){
            this.end = end;
            this.dis = dis;
        }
    }
}