[백준] 1948. 임계경로 (Java)

 

문제

1948번: 임계경로

 

알고리즘

그래프, 위상 정렬

 

풀이

위상 정렬을 통해 마지막 노드까지 가는데 걸리는 시간의 최댓값을 구하고,

해당 최댓값을 만드는 경로에 있는 간선의 수를 출력하는 문제이다.

 

크기가 n를 배열을 만들어 각 도시까지 가는 최댓값을 저장한다.

이를 이용해 다음 도시로 가는데 걸리는 최댓값을 알 수 있다.

 

예제 입력 1로 표현하면 다음과 같다.

각 도시까지 가는데 걸리는 비용의 최댓값

예제 입력 1 그래프

 

최댓값을 구했다면 이제 최댓값을 만드는 경로를 찾아야하는데 이는 도착 도시에서부터 역추적한다.

 

도착 도시 7까지 오는 최댓값이 12였다.

이는 도시 6까지 오는 최댓값 7에, 6에서 7로 가는 비용 5가 더해진 값이다.

 

도시 6까지 오는 최댓값 7은

도시 2까지 오는 최댓값 4에, 2에서 6으로 가는 비용 3이 더해진 값과

도시 4까지 오는 최댓값 3에, 4에서 6으로 가는 비용 4가 더해진 값이다.

 

도시 2까지 오는 최댓값 4는 도시 1에서 오는 비용 4이다.

도시 4까지 오는 최댓값 3은 도시 1에서 오는 비용 3이다.

 

이렇게 도착 도시의 최댓값을 만드는, 즉 제일 늦게 도착하기 때문에 1분도 쉬지 않고 달려야하는 도로 5개를 찾았다.

 

이를 구현하기 위해서

각 노드 사이의 간선들을 입력받고 저장할 때, 역추적을 위해 반대 방향으로도 저장한다.

 

이제 도착 도시에서부터 너비우선탐색을 진행하는데 저장해놓은 도시까지의 최댓값을 이용한다.

max[7] = 12 이고, 7에 연결된 노드는 2와 6이 있다.

7에서 2로 가면서 가중치가 max[7] - max[2] = 8 인 간선이 있다면 해당 간선이 쉬지 않고 달려야하는 도로이지만 존재하지 않는다.

반면 7에서 6으로 가면서 가중치가 max[7] - max[6] = 5 인 간선은 존재하므로 count 를 1 증가시키고 해당 연결된 노드인 6번 노드를 큐에 삽입한다.

 

이때 간선이 중복으로 count 되지 않도록 방문 처리를 해야하는데,

큐에 삽입할 때 방문 체크하는 것이 아닌 큐에서 꺼낼 때 방문 체크해야 올바른 답을 구할 수 있다.

 

큐에 삽입할 때 방문 체크를 한다면 위 예제에서 7->6->2->1 경로를 통해 7,6,2,1번 노드가 방문 처리되어있고,

이로 인해 7->6->4->1 경로에서 1번 노드가 이미 방문처리되어있어 4->1 간선이 체크되지 않을 것이다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

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

		ArrayList<Node>[] graph = new ArrayList[n + 1];
		ArrayList<Node>[] rgraph = new ArrayList[n + 1];

		for (int i = 1; i <= n; i++) {
			graph[i] = new ArrayList<>();
			rgraph[i] = new ArrayList<>();
		}

		int[] inDegree = new int[n + 1];
		int[] mdist = new int[n + 1];
		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 t = Integer.parseInt(st.nextToken());

			graph[s].add(new Node(e, t));
			rgraph[e].add(new Node(s, t));
			inDegree[e]++;
		}

		st = new StringTokenizer(br.readLine(), " ");
		int startIndex = Integer.parseInt(st.nextToken());
		int endIndex = Integer.parseInt(st.nextToken());

		ArrayDeque<Node> deque = new ArrayDeque<>();
		deque.add(new Node(startIndex, 0));

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

			for (Node next : graph[cur.id]) {
				mdist[next.id] = Math.max(mdist[next.id], cur.time + next.time);
				if (--inDegree[next.id] == 0) {
					deque.add(new Node(next.id, mdist[next.id]));
				}
			}
		}

		boolean[] visited = new boolean[n + 1];
		ArrayDeque<Node> rdeque = new ArrayDeque<>();
		rdeque.add(new Node(endIndex, 0));
		
		int ans = 0;
		while (!rdeque.isEmpty()) {
			Node cur = rdeque.poll();
			
			if(visited[cur.id]) continue;
			visited[cur.id] = true;
			
			for(Node next: rgraph[cur.id]) {
				if(mdist[cur.id] - next.time == mdist[next.id]) {
					ans++;
					rdeque.add(new Node(next.id, 0));
				}
			}
		}

		System.out.println(mdist[endIndex]);
		System.out.println(ans);
	}

	static class Node {
		int id, time;

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