[BOJ] - 임계경로 / 1948번 (Java)

[BOJ] - 임계경로 / 1948번 (Java)

[BOJ] - 임계경로 / 1948번 (Java)

1. 문제 접근

사이클이 없는 유향 그래프가 주어 질 때, 가장 마지막에 도착하는 시간과 그러한 사람들이 거쳐온 경로의 개수를 구하면 된다.

"즉 전체 공정 중 가장 시간이 많이 걸리는 경로이다. 각 작업의 공정을 그래프 형태로 나타냈을 때 임계 경로는 시작점에서 종료점에 이르는 가장 긴 경로가 된다."
출처 - [TTA정보통신 용어사전]

 

"사이클이 없는 유향그래프"로 부터  위상 정렬을 사용하여 최장 거리를 수할 수 있음을 알 수 있다.

 

문제는 최장거리는 쉽게 구할 수 있지만, 임계경로의 개수를 어떻게 구해야하는 것에 대한 발상이 어려웠다.

 

정방향(출발지 -> 도착지)의 위상정렬을 구해가며 모든 경로를 노드에 저장해가며 풀어야하나 생각도 했지만, 서로 다른 두 임계경로가 하나의 간선을 공유하는 경우를 처리하는 것이 불가능했다.

 

따라서 임계경로의 문제는 역방향(도착지 -> 출발지)의 위상정렬을 통해 사용 간선의 수를 구하는  아이디어를 참고하여 문제에 접근하였다.

 

알고리즘의 흐름은 아래와 같다.

1. 정방향의 위상정렬을 수행하며 출발지로부터 모든 정점까지의 최장거리를 구한다.
2. 역방향의 위상정렬을 수행하며 정방향과 동일하게 도착지로부터 모든 정점까지의 최장거리를 구한다.
   
   1. 특정 정점을 조회한다.
   2. 해당 노드의 간선을 모두 조회한다.
   3. `조회한 간선의 목적지 노드의 정방향 최대거리 +( 현재 정점의 역방향 최대거리 + 간선의 가중치) == 최장거리`를 만족하는지 확인한다.
   4. 만족한다면 해당 간선은 임계경로이므로 카운팅한다.

// 출발지로부터 해당 정점까지의 최대거리 + 도착지로부터 해당 정점까지의 최대거리 == 최대거리일 경우
// 해당 간선은 임계경로에 포함되는 간선
if ((reverseDist[currNode] + weight) + dist[adNode] == maxDist) {
    ans++;
}

 

A 노드 ------(간선의 가중치)------ B노드

 

위와 같은 형태의 간선을 보면, A노드까지의 최장거리와 B노드까지의 최장거리가 구해졌을 때 주어진 간선이 임계경로에 포함되기 위한 조건은 A노드까지의 최장거리 + B노드까지의 최장거리 + 간선의 길이(가중치)가 총 최정거리와 동일할 때다.

 

따라서 정방향의 위상정렬, 역방향의 위상정렬을 순서대로 수행하며 위 조건에 해단되는 간선의 수를 카운팅 해나갔다.

 

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * [BOJ] - 임계경로 / 1948번 
 * @author JinHxxxxKim
 * 
 * 1. 정방향 그래프를 위상정렬을 통해 각 정점까지의 최대 거리를 구한다.
 * 		1-1. 도착지까지의 최대 거리를 구한다.
 * 2. 역방향 그래프를 통해 위상정렬을 실행한다.
 * 		2-1. 위상 정렬을 실행하며, 탐색하는 노드까지의 최대거리 + 정방형의 최대 거리 = 최대거리인지 확인한다.
 * 		2-2. 맞다면 해당 간선은 임계경로로 판단, ans+1을 한다.
 */
public class Sol_1948 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static int nodeNum; // 정점의 개수
	private static int edgeNum; // 간선의 개수
	private static int startNode; // 시작 정점
	private static int endNode; // 종료 정점
	private static List<Edge>[] adList; // 정방향 인접리스트
	private static List<Edge>[] reverseAdList; // 역방향 인접리스트
	private static int[] inDegree; // 정방향 진입차수
	private static int[] reverseInDegree; // 역방향 진입차수
	private static int[] dist; // 정방향 각 정점까지 최대 거리
	private static int[] reverseDist; // 역방향 각 정점까지 최대거리
	private static int maxDist; // 도착지까지의 최대 경로
	private static int ans;

	public static void main(String[] args) throws Exception {
		nodeNum = Integer.parseInt(br.readLine().trim());
		edgeNum = Integer.parseInt(br.readLine().trim());
		adList = new List[nodeNum + 1];
		reverseAdList = new List[nodeNum + 1];
		inDegree = new int[nodeNum + 1];
		reverseInDegree = new int[nodeNum + 1];
		dist = new int[nodeNum + 1];
		reverseDist = new int[nodeNum + 1];

		for (int node = 1; node < nodeNum + 1; ++node) {
			adList[node] = new ArrayList<>();
			reverseAdList[node] = new ArrayList<>();
		}

		for (int edgeCnt = 0; edgeCnt < edgeNum; ++edgeCnt) {
			st = new StringTokenizer(br.readLine().trim());
			int srcNode = Integer.parseInt(st.nextToken());
			int destNode = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());

			adList[srcNode].add(new Edge(destNode, weight));
			inDegree[destNode]++;
			reverseAdList[destNode].add(new Edge(srcNode, weight));
			reverseInDegree[srcNode]++;
		}

		st = new StringTokenizer(br.readLine().trim());
		startNode = Integer.parseInt(st.nextToken());
		endNode = Integer.parseInt(st.nextToken());

		// 정방향 위상정렬 시작
		Queue<Integer> q = new ArrayDeque<>();
		q.add(startNode);
		while (!q.isEmpty()) {
			int currNode = q.poll();
			// currNode에 연결 된 간선 확인
			for (Edge currEdge : adList[currNode]) {
				int adNode = currEdge.destNode;
				int weight = currEdge.weight;
				inDegree[adNode]--;
				if (inDegree[adNode] == 0) {
					q.offer(adNode);
				}
				// 최대 거리 갱신
				dist[adNode] = Math.max(dist[adNode], dist[currNode] + weight);
			}
		}
		maxDist = dist[endNode];

		// 역방향 위상정렬 시작
		q = new ArrayDeque<>();
		q.add(endNode);
		while (!q.isEmpty()) {
			int currNode = q.poll();
			// currNode에 연결 된 간선 확인
			for (Edge currEdge : reverseAdList[currNode]) {
				int adNode = currEdge.destNode;
				int weight = currEdge.weight;
				reverseInDegree[adNode]--;
				if (reverseInDegree[adNode] == 0) {
					q.offer(adNode);
				}
				// 출발지로부터 해당 정점까지의 최대거리 + 도착지로부터 해당 정점까지의 최대거리 == 최대거리일 경우
				// 해당 간선은 임계경로에 포함되는 간선
				if ((reverseDist[currNode] + weight) + dist[adNode] == maxDist) {
					ans++;
				}
				// 최대 거리 갱신
				reverseDist[adNode] = Math.max(reverseDist[adNode], reverseDist[currNode] + weight);
			}
		}
		System.out.println(maxDist);
		System.out.println(ans);
	}

	// 간선 클래스
	static class Edge {
		int destNode;
		int weight;

		public Edge(int destNode, int weight) {
			super();
			this.destNode = destNode;
			this.weight = weight;
		}
	}
}

---

3. 디버깅

최근 다양한 문제를 풀며 알고리즘에 자신감이 올라와서 도전해 본 문제였지만, 키보드를 쳐보지도 못하고 꺾여버렸다.

 

임계경로에 대한 개념이 하나도 잡혀있지 않아 역방향 위상정렬에 대한 아이디어를 떠올리지 조차 못했다.

 

다른 풀이를 보게 되면 역방향 위상정렬을 수행하며 모든 정점을 큐에 넣지 않고, 임계경로에 포함될 수 있는 유망한 정점만 삽입을 하는 것을 보게 되었다.

 

나의 풀이처럼 정방향 최대거리(`dist[]`), 역방향 최대거리(`reverseDist[]`)를 모두 사용하는 것이 아닌, 정방향 최대거리(`dist[]`)만을 사용하고, 간선에 더 집중하여 최적화여 구현하였다.

 

임계경로의 개념에 대해 익히고, 아직도 많이 부족함을 느낀 문제였다.

 

---

4. 결과