[BOJ] 1516. 게임 개발

위상정렬을 이용하여 풀은 문제였다.

문제를 맨처음 파악했을때, 일의 우선순위가 있고, 일끼리 싸이클을 만들지 않는 DAG임을 보장받을 수 있는 조건이라 위상정렬을 사용하여 문제를 풀었다. 이 문제에선 우선순위가 높은것 -> 우선순위가 낮은것 으로 간선을 연결해 주었고, indegree배열과 queue를 이용하여 위상정렬을 구현하였다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_1516_게임개발 {
    static int N;
    static int[] indegree;
    static int[] time;
    static int[] result;
    static List<Integer>[] graph;
//    static List<Integer>[] reverse;
    
    static Queue<Integer> queue;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N=Integer.parseInt(br.readLine());
        
        indegree=new int[N+1];
        time=new int[N+1];
        result=new int[N+1];
        graph=new ArrayList[N+1];
//        reverse=new ArrayList[N+1];
        for(int i=1;i<=N;i++) {
            graph[i]=new ArrayList<>();
//            reverse[i]=new ArrayList<>();
        }
        
        for(int i=1;i<=N;i++) {
            st=new StringTokenizer(br.readLine());
            time[i]=Integer.parseInt(st.nextToken());
            while(true) {
                int v=Integer.parseInt(st.nextToken());
                if(v==-1)
                    break;
                graph[v].add(i);
//                reverse[i].add(v);
                indegree[i]+=1;
            }
        }
        
        queue=new LinkedList<>();
        for(int i=1;i<=N;i++) {
            if(indegree[i]==0) {
                queue.offer(i);
                result[i]=time[i];
            }
        }
        topological();
        
        for(int i=1;i<=N;i++)
            System.out.println(result[i]);
    }
    
    static void topological() {
        while(!queue.isEmpty()) {
            int cur=queue.poll();
            
//            int timeMax=0;
//            for(int reve :reverse[cur]) {
//                timeMax=Math.max(timeMax, result[reve]);
//            }
//            result[cur]=time[cur]+timeMax;
            
            for(int next:graph[cur]) {
            
                result[next]=Math.max(result[next], result[cur]+time[next]);
                
                indegree[next]-=1;
                if(indegree[next]==0) {
                    queue.offer(next);
                }
            }
        }
    }
    
}