BOJ_1948 : 임계경로

👉 문제링크

---

 

---

🔸 문제 분석 🔸

• N개의 도시 사이 M개의 도로가 주어진다. 각 도로를 건너는 시간이 있고, 출발지와 도착지가 주어진다.
• 도로는 출발지부터 도착지까지 단방향 비순환 그래프이다.
• 많은 경로 중에 가장 늦게 도착하는 경로에서 지나는 도로의 수 총합을 출력한다.

🔸 문제 풀이 🔸

• 출발지부터 도착지까지 단방향 비순환 그래프이므로, 위상 정렬(Topology Sort)을 통해 최대값을 구할 수 있다.
• 건너온 경로의 수를 카운트 해야하므로 역방향 탐색이 필요하다.
  • 1분도 쉬지 않고 달린 경로이므로 현재 시간과 도로의 소요 시간의 차이가 맞아 떨어져야 한다.
  • 경로를 중복되게 체크하지 않기 위해서 도시를 방문처리 한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[] indegree = new int[n + 1];

        ArrayList<ArrayList<Edge>> adjList = new ArrayList<>();
        ArrayList<ArrayList<Edge>> adjList_reverse = new ArrayList<>();

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int out = Integer.parseInt(st.nextToken());
            int in = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            adjList.get(out).add(new Edge(in, time));
            adjList_reverse.get(in).add(new Edge(out, time));
            indegree[in]++;
        }

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


        // 위상 정렬
        int[] critical_path = new int[n + 1]; // 걸린 시간의 최댓값
        Queue<Integer> que = new ArrayDeque<>();
        que.offer(start);

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

            for (Edge next : adjList.get(now)) {
                critical_path[next.v] = Math.max(critical_path[next.v], critical_path[now] + next.time);
                if (--indegree[next.v] == 0) {
                    que.offer(next.v);
                }
            }
        }

        // 역방향 위상 정렬
        boolean[] visited = new boolean[n + 1];
        que.offer(end);
        int cnt = 0;

        while (!que.isEmpty()) {
            int now = que.poll();
            for (Edge next : adjList_reverse.get(now)) {
                if (critical_path[now] == critical_path[next.v] + next.time) {
                    cnt++;
                    if (!visited[next.v]) {
                        que.offer(next.v);
                        visited[next.v] = true;
                    }
                }
            }
        }

        sb.append(critical_path[end]).append('\n').append(cnt);
        bw.write(sb.toString());
        bw.flush();
    }

    private static class Edge {
        int v;
        int time;

        public Edge(int v, int time) {
            this.v = v;
            this.time = time;
        }
    }
}

🔸 코드 해석 🔸

• 진입 차수 int형 배열 indegree, 인접 리스트 adjList와 역방향 인접 리스트 adjList_reverse를 입력받는다.
• 먼저 위상 정렬을 통해 각 도시에 도착하는 최대 시간(임계 경로)를 구한다.
  • 현재 도시에서 다음 도시로 가는 경로가 더 큰 값이면 업데이트 (DP 느낌)
  • 다음 도시의 진입 차수를 -1 해주고, 만약 0이 되었다면 경로를 확인하기 위해 큐에 넣는다.
  • 최종 도착지의 임계 경로 값이 도착까지 걸리는 최대 시간이다.
• 역방향 위상 정렬을 통해 건너온 간선의 수를 카운트한다.
  • 순방향 위상 정렬과 다른 점은, 1분도 기다려서는 안되기 때문에 시간이 정확히 일치해야 한다.
    (다음 도시로 가는 시간 + 다음 도시 임계 경로값 = 현재 도시 임계 경로값)
  • 일치한다면, 해당 경로가 지나온 길이므로 cnt+1
  • 중복을 피하기 위해 방문 체크로 1번만 다음 도시를 큐에 넣는다.
  • 총 카운트 된 cnt 값이 지나온 경로의 총합이다.

---

🔸 end 🔸

• 위상 정렬 알고리즘을 공부하며 최종으로 풀어본 어려운 문제인데...너무 어려웠다.
• 3시간은 잡고있던 것 같은데, 위상 정렬을 완벽히 이해하고, 그래프 문제에서 종종 나오는 역방향 탐색까지 필요로 했다.
• 알고리즘은 간단하다고 생각했는데, 활용 영역이 너무 다양해서 아직 한참 연습이 필요한 것 같다.