백준 1005번 (java) 위상정렬

백준 1005번: ACM Craft JAVA

---

관찰

순서가 정해져있고 순서를 따라야 하는 문제라서 위상정렬로 풀면 될 거 같다!

하지만 단순 위상정렬로 값을 다 더해버리면 안된다
하나의 건설이 끝나면 동시에 건설을 시작할 수 있다는 조건이 있다!

위상정렬로 도는 동안 도착한 노드의 최대값을 저장해두자!

정답코드

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

public class Main {
    static int  T, // 테스트 케이스
                n, // 건물의 갯수
                k, // 규칙의 갯수
                goal; // 목표 건물
    static int[] time, // 건물이 지어지는 시간
                 inDeg, // 진입차수
                 maxTime; // 가장 큰 값 찾기
    static List<Integer>[] eList; // 단방향 그래프
    static Queue<Integer> que;// 위상 정렬을 위한 queue
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            time = new int[n+1];
            inDeg = new int[n+1];
            maxTime = new int[n+1];
            eList = new List[n+1];
            que = new LinkedList<>();
            for(int i=1;i<n+1;i++){
                eList[i] = new ArrayList<Integer>();
            }
            st = new StringTokenizer(br.readLine());
            for(int i=1;i<n+1;i++){
                time[i] = Integer.parseInt(st.nextToken());
            }
            for(int i=0;i<k;i++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                inDeg[b]++;
                eList[a].add(b);
            }
            goal = Integer.parseInt(br.readLine());

            // 진입 차수가 0인 정점을 q에 넣기
            for(int i=1;i<n+1;i++){
                if(inDeg[i] == 0) {
                    que.offer(i);
                    maxTime[i] = time[i];
                }
            }
            // 위상정렬
            while(!que.isEmpty() && inDeg[goal] != 0){
                int cur = que.poll();
                for(int next : eList[cur]){
                    inDeg[next]--;
                    maxTime[next] = Integer.max(maxTime[cur]+ time[next],maxTime[next]);
                    if(inDeg[next] == 0) que.offer(next);
                }
            }
            sb.append(maxTime[goal]).append("\n");
        }
        System.out.println(sb);
    }
}

풀이

위상정렬을 통해 노드에 도착할 때마다 기존값과 공사시간을 더한 값 중 큰 값만 넣으면서 채워준다!

그리고 목표의 maxTime 값을 출력해주면 답!

느낀점

뭔가 문제가 너무 억지스러워서 이해하는데 시간이 많이 갔다..

문제에서 최소시간을 찾으라고 했지만 역설적으로 최대값을 저장하는 과정에서 답을 찾을 수 있었다 훼이크인 느낌..?