[알고리즘_코딩 테스트_JAVA] 그래프-임계 경로 구하기 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 055 임계 경로 구하기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

▪️ 위상정렬, 에지 뒤집기

플래티넘 문제인 만큼 문제 의미 해석부터 어려웠던 문제이다. (그만큼 깨달은게 많아 별도 문제로 기록한다..ㅎ)

여기서 임계 경로는 최장거리를 의미한다. 이 문제에서, 모든 사람들이 만나는 시간은 도착점에 가장 오래걸리는 사람이 도착하는 시간일 것이다. 만약 1 → 3 (2초) 2 → 3 (10) 초라고 가정해보자. 그럼 모든 사람들이 만나는 시간은 2->3 인 10초일것이다. 즉, 문제에서 요구하는 '출발 도시에서 출발한 후 도착 도시에서 만나기까지 걸리는 최소시간'은 '도착점에 가장 늦게 도착했을때 걸리는 시간(최장 시간)'이다. 이는 최장 경로비용을 의미한다.

또한 문제에서는 일방통행이고 사이클이 없다고 했다. 이 조건을 보고 위상정렬을 떠올릴 수 있다. 노드들의 순서가 있고 그 순서에 따라야 하기 때문이다.

 

또한 역방향 위상정렬을 활용하면 도착 도시에서 출발하여 출발 도시까지 가는 임계 경로를 찾아나갈 수 있다. 그 방법은 다음과같다.

먼저 에지를 뒤집어,역방향 인접리스트를 만들어둔다.  그리고 각 노드의 누적 최장시간 비용을 계산해둔다. 이제 이 정보를 바탕으로, 역방향으로 7에서부터 목적지까지 역으로 위상정렬을 시작해보자. 7은 최장 시간이 12이고 7에서 최장도로 후보는 7과 연결된 도로 7→6, 7 → 2이다.  차례로 후보 6,2를 보자.

 

6번 도시:

• 7번 도시 최장 시간은 12
• 6번 도시에서 도착 도시까지 가는 최장 시간은 12 (6번의 최장시간 + 6→7 도로시간)
• 현재 도시의 최소 도착 시간 (최장 비용) == 이전 도시의 최소도착시간 + 해당 도로(엣지)의 시간. 따라서 6번 도시는 임계 경로에 포함된다. 그러므로 q에 삽입.

2번 도시:

• 7번 도시 최장 시간은 12
• 2번 도시에서 도착 도시까지 가는 최장 시간은 4 + 5 = 9 (2번의 최장시간 + 6→7 도로시간)
• 2번 도시는 임계 경로에 포함되지 않는다.

이제 6을 보자. 6에서 연결노드는 2, 5, 4이고 6의 최장 시간은 7이다. 7에서 했던것처럼, 위 과정을 출발 노드에 도달할때까지 반복한다.

 

▪️구현 핵심

1. [그림1] 인접 리스트에 노드 데이터를 저장하고, 진입 차수 리스트 값을 업데이트 한다. 이 때 에지 방향이 반대인 역방향 인접 리스트도 함께 생성하고 저장한다.
2. [그림1~그림2] 시작 노드에서부터 위상 정렬을 수행해나가며, 각 도시와 관련된 임계 경로를 누적하며 저장한다. 즉, 위상 정렬된 순서대로 방문하면서 각 도시 시간 최댓값을 취하여 기록한다.
3. [그림2~그림3] 도착 도시에서부터 역방향으로 위상 정렬을 수행한다. 이때 다음은 '1분도 쉬지 않고 달려야 하는 도로'로 카운팅하고, 큐에 삽입한다. ; 현재 도시의 최소 도착 시간 (최장 비용) == 이전 도시의 최소도착시간 + 해당 도로(엣지)의 시간
4. 이때, 정답 도로 수 중복 카운팅 방지를 위해 이미 방문한 적이 있는 노드는 큐에 넣지 않는다!

그림1 , 그림 2, 그림 3

슈도코드 작성하기

N(도시 수), M(도로 수)
A(도시 인접 리스트), reverseA(역방향 인접 리스트)
indegree(진입 차수 리스트)

for M 도로수만큼 반복:
    인접 리스트 데이터 저장
    역방향 인접 리스트 데이터 저장
    진입 차수 리스트 저장

시작, 도착 도시 데이터 받기

# 위상 정렬 수행
큐 생성
출발 도시 큐 삽입
result(결괏값)

while 큐가 빌 때까지:
    현재 노드 = 큐에서 데이터 가져오기
    for 현재 노드에서 갈 수 있는 노드 탐색:
        타깃 노드 진입 차수 -=1
        result = max(타깃 노드 현재 최장 시간, 현재 노드 경롯값 + 현재 노드~타깃노드 도로 시간 값)
        if 타깃 노드 진입 차수 0:
            큐에 타깃 노드 추가

resultCount(1분도 쉬지 않고 달려야 하는 도로의 수)

visited(각 도시 방문 유무 저장)
도착 도시 큐에 삽입
visited 리스트에 도착 도시 방문 도시 표시

# 위상 정렬 역방향 수행
while q:
    현재 노드 = 큐에서 데이터 가져오기
    if 현재 노드 result + 도로를 걸리는 데 지나는 시간(에지) == 타깃 노드 result값:
        resultCount(1분도 쉬지 않고 달려야 하는 도로 값) 1 증가
        if 아직 방문하지 않은 도시:
            visited 리스트에 방문 도시 표시
            큐에 타깃 노드 추가
            
만나는 시간(result[endDosi]) 출력
1분도 쉬지 않고 달려야 하는 도로 수(resultCount) 출력

JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<dNode>> A = new ArrayList<>();
        ArrayList<ArrayList<dNode>> reverseA = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            A.add(new ArrayList<>());
            reverseA.add(new ArrayList<>());
        }
        int[] indegree = new int[N + 1]; // 진입 차수 배열
        for (int i = 0; i < M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            A.get(S).add(new dNode(E, V));
            reverseA.get(E).add(new dNode(S, V)); // 역방향 에지 정보 저장
            indegree[E]++; // 진입 차수 배열 초기화
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int startDosi = Integer.parseInt(st.nextToken());
        int endDosi = Integer.parseInt(st.nextToken());
        // 위상 정렬
        Queue<Integer> q = new LinkedList<>();
        q.offer(startDosi);
        int[] result = new int[N + 1];
        while (!q.isEmpty()) {
            int now = q.poll();
            for (dNode next : A.get(now)) {
                indegree[next.targetNode]--;
                result[next.targetNode] = Math.max(result[next.targetNode], result[now] + next.value);
                if (indegree[next.targetNode] == 0) {
                    q.offer(next.targetNode);
                }
            }
        }
        // 위상 정렬 reverse
        int resultCount = 0;
        boolean[] visited = new boolean[N + 1];
        q = new LinkedList<>();
        q.offer(endDosi);
        visited[endDosi] = true;
        while (!q.isEmpty()) {
            int now = q.poll();
            for (dNode next : reverseA.get(now)) {
                // 1분도 쉬지 않는 도로 체크
                if (result[next.targetNode] + next.value == result[now]) {
                    resultCount++;
                    // 중복 카운트 방지를 위해 이미 방문한 적 있는 노드 제외
                    if (!visited[next.targetNode]) {
                        visited[next.targetNode] = true;
                        q.offer(next.targetNode);
                    }
                }
            }
        }
        System.out.println(result[endDosi]);
        System.out.println(resultCount);
    }

    static class dNode {
        int targetNode;
        int value;
        dNode(int targetNode, int value) {
            this.targetNode = targetNode;
            this.value = value;
        }
    }
}

PYTHON

import sys
from collections import deque
input = sys.stdin.readline

N = int(input()) # 도시 수
M = int(input()) # 도로 수
A = [[] for _ in range(N + 1)]
reversedA = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1) # 진입 차수 리스트

for i in range(M):
    S, E, V = map(int, input().split())
    A[S].append((E, V)) # 연결노드, 가중치
    reversedA[E].append((S,V)) # 역방향 에지 정보 저장
    indegree[E] += 1 # 진입 차수 저장

startDosi,endDosi = map(int, input().split())

q = deque() # 큐 초기화
q.append(startDosi)
result = [0] * (N + 1)

# 위상정렬
while q:
    now = q.popleft()
    for next in A[now]:
        indegree[next[0]] -= 1
        # 연결노드 임계경로값 vs 현재노드 임계 경로값 + 현재~연결노드 사이 경로값
        result[next[0]] = max(result[next[0]], result[now] + next[1])
        if indegree[next[0]] == 0:
            q.append(next[0])
            
resultCount = 0
visited = [False] * (N + 1)
q.clear()
q.append(endDosi)
visited[endDosi] = True

# 위상정렬 reverse 수행
while q:
    now = q.popleft()
    for next in reversedA[now]:
        # 1분도 쉬지 않는 도로 체크
        if result[next[0]] + next[1] == result[now]: # ex_ 6(next) <- 7(now)
            resultCount += 1 # 1분도 쉬지않는 도로수 + 1
            if not visited[next[0]]:
                visited[next[0]] = True
                q.append(next[0])
                
print(result[endDosi])
print(resultCount)