백준 1948 임계경로

문제

풀이

import java.io.*;
import java.util.*;

public class Q1948_임계경로 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 도시 수
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        // 도로 개수
        int m = Integer.parseInt(st.nextToken());
        ArrayList<cNode>[] arr = new ArrayList[n + 1];
        ArrayList<cNode>[] reverse = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
            reverse[i] = new ArrayList<>();
        }
		
        // 각 에지 정보를 정방향, 역방향 배열에 모두 저장
        int[] edge = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int tmp = Integer.parseInt(st.nextToken());
            arr[s].add(new cNode(e,tmp));
            reverse[e].add(new cNode(s,tmp));
            edge[e]++;
        }
        
        st = new StringTokenizer(br.readLine());
        // 출발 도시
        int start = Integer.parseInt(st.nextToken());
        // 도착 도시
        int end = Integer.parseInt(st.nextToken());

        // 먼저 위상 정렬을 진행해줌
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        int[] result = new int[n + 1];
        while (!q.isEmpty()) {
            int now = q.poll();
            for (cNode next : arr[now]) {
                edge[next.target]--;
                // 모두 다시 만나려면 제일 늦게 도착한 사람을 찾아야 함
                // 따라서 노드에는 도착 소요시간 중 최대 값을 저장
                result[next.target] = Math.max(result[next.target], result[now] + next.value);
                if (edge[next.target] == 0) {
                    q.add(next.target);
                }
            }
        }

        // 위상정렬 반대로 수행
        int cnt = 0;
        /* 1분도 쉬지 않고 달린 사람이 타겟이므로
       	현재 노드의 임계경로 값 == 이전 노드의 임계경로 값 + 현재 노드 도달 소요시간
        위의 조건이 성립되어야 한다.
        이때 조건을 만족하는 진입 차수가 둘 이상일 수 있으므로
        이미 접근 했던 노드인지 확인이 필요함 */
        boolean visited[] = new boolean[n + 1];
        q = new LinkedList<>();
        q.add(end);
        visited[end] = true;
        while (!q.isEmpty()) {
            // 여기서 now는 도착 도시
            int now = q.poll();
            // 여기서 next는 출발 도시
            for (cNode next : reverse[now]) {
                // 출발 노드의 임계값 + 출발 노드의 value == 도착 노드의 임계값
                if (result[next.target] + next.value == result[now]) {
                    // 1분도 쉬지 않았다는 뜻이므로 cnt + 1
                    cnt++;
                    // 출발 노드가 겹칠 수 있으므로 중복 체크
                    if (visited[next.target] == false) {
                        // 방문 기록을 남기고 출발 노드를 큐에 삽입
                        visited[next.target] = true;
                        q.add(next.target);
                    }
                }
            }
        }
        // 사람들이 만나는 시간
        System.out.println(result[end]);
        // 1분도 쉬지 않고 달려야 하는 도로의 수
        System.out.println(cnt);
    }
}

class cNode{
	// 다음 노드
    int target;
    // 이동 소요 시간
    int value;

    public cNode(int next, int value) {
        this.target = next;
        this.value = value;
    }

}

리뷰

위상정렬을 적용해 풀어야 하는 문제였는데,
단순히 위상정렬만 이용하는게 아니라,
1분도 쉬지 않고 달려야 하는 도로의 수를 구하기 위해 엣지 뒤집기를 구현해야 했다.
엣지 뒤집기라는 개념(?)은 처음 봤는데 괜히 플레티넘 문제가 아니구나 싶었다.

1. 먼저 리스트에 노드 데이터를 저장하고, 진입 차수를 기록한다.
   • 이 때 엣지 뒤집기를 위해 반대방향으로도 노드 데이터를 저장해준다.
2. 위상정렬을 먼저 진행한다.
   • 임계 경로값을 갱신해주는데, 모두 다시 만나려면 시간이 가장 오래 걸린 사람이 도착해야 하므로 임계경로 중 최대값으로 갱신해준다.
3. 엣지를 뒤집어 위상정렬을 다시 진행한다.
   • 여기서 1분도 쉬지 않고 달려야 하는 도로를 구한다.
     1분도 쉬지 않고 달린 도로라는 뜻은
     '현재 노드의 소요 시간 + 앞선 노드까지의 임계값 == 현재 노드의 임계값'
     이라는 뜻이므로 이 조건에 만족하는 노드는 카운트하고, 탐색을 진행한다.
   • 이때 동일한 노드를 중복으로 탐색하지 않기 위해 해당 노드를 방문했는지 여부를 체크한다.
4. 마지막으로 사람들이 만나는 시간과
   1분도 쉬지 않고 달려야 하는 도로의 수를 출력한다.