백준 | 1948번. 임계경로 - 위상정렬 & 다익스트라

⬛ 백준 1948번. 임계경로 - 위상정렬

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

1948번: 임계경로

문제

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

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

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

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

입력

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

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

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

출력

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

---

💚나의 풀이 - 문제 뜻 파악 중요

1) 1분도 쉬지 않고 달려야 하는 사람까지 포함했을 때 모두가 만날 수 있는 최소 시간

• 즉, 가장 긴 시간이 걸리는 임계 경로의 시간을 구하라.

2) 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수 

• 임계 경로가 거치는 도로의 수(임계 경로로 거치는 도시)

→ 1) 의 경우, 시작점과 도착점까지 거치는 일반적인 정방향 위상 정렬로 가장 긴 시간 걸리는 시간 구하면 된다.

→ 2) 의 경우, 역방향으로 그래프 뒤집어서, 특정 정점이 가장 긴 경로에 속하는 정점인지 확인하면 된다.

• 아래의 조건을 만족하는 정점들을 카운팅. 그 정점들을 거쳐서 가장 긴 경로를 간다는 뜻이므로.

//역방향으로 가면서 
**직전 도시 임계경로값 == 다음 도시 임계경로값 + 둘 사이 시간**

• 어렵다

import java.util.*;

/*2948번. 임계경로 구하기 */
class Node{
	int target;
	int value;
	Node(int target, int value){
		this.target = target;
		this.value = value;
	}
}
public class Main {
	static int N, M;
	static int[] indegree;
	//정방향 그래프 
	static ArrayList<ArrayList<Node>> A;
	//역방향 그래프
	static ArrayList<ArrayList<Node>> reverseA;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		indegree = new int[N+1];
		
		A = new ArrayList<>();
		reverseA = new ArrayList<>();
		
		for(int i=0; i<=N; i++) {
			A.add(new ArrayList<>());
			reverseA.add(new ArrayList<>());
		}
		
		//데이터 입력받기 
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int val = kb.nextInt();
			//정방 입력 
			A.get(a).add(new Node(b, val));
			//역방 입력
			reverseA.get(b).add(new Node(a, val));
			
			//진입차수 
			indegree[b]++;//찐 진입차수 ++ 처리 
		}
		
		//출발도시 도착도시 입력 
		int start = kb.nextInt();
		int end = kb.nextInt();
		
		//위상정렬 알고리즘 시작 =====> 
		Queue<Integer> Q = new LinkedList<>();
		
		//시작점 처리
		Q.offer(start);
		//가장 긴 임계경로 구하기 위해 각 도시로 가는 정점 - 다익스트라로 풀기 
		int[] result = new int[N+1];
		
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			for(Node nx : A.get(cur)) {
				int target = nx.target;
				int val = nx.value;
				//기존 값 vs cur정점 거쳐가는 값 중 큰 값으로 세팅 
				result[target] = Math.max(result[target], result[cur]+val);
				indegree[target	]--;
				
				if(indegree[target]==0) {
					Q.offer(target);
				}
			}
		}
		
		//역방향 위상정렬 처리 
		int resultCnt = 0;//도시 개수 
		boolean[] visited = new boolean[N+1];
		Q = new LinkedList<>();
		
		Q.offer(end);//도착점부터 역으로 거쳐가기
		visited[end] = true;
		
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			for(Node nx : reverseA.get(cur)) {
				//하나씩 역순으로 가면서 체킹
				if(result[nx.target] + nx.value == result[cur]) {
					resultCnt++;
					//중복 카운팅 방지 위하여 이미 방문한 곳은 체킹
					if(visited[nx.target]== false) {
						visited[nx.target] = true;
						Q.offer(nx.target);
					}
				}
			}
		}
		
		//정답 세팅 
		System.out.println(result[end]);//가장 긴 임계경로 시간 
		System.out.println(resultCnt);//그 도시 개수 
	}
}