[BOJ] 백준 1516 - 게임 개발 (자바)

위상정렬 (Topological Sort) 의 가장 대표적인 문제

위상정렬 뿐 아니라 배열 두개를 더 만들어서 각각의 시간을 저장해야한다.

배열 1 : 원래의 값들(건물 짓는데 걸리는 시간)을 저장하는 배열

배열 2 : 최소의 시간을 구하기 위한 배열 (이전의 건물 짓는데 걸린 시간을 더해야한다. 그로므로 배열 1만 사용하는 것은 불가능.. 코드 괴물들은 가능할지도?)

그리고 이번 위상정렬 문제는 입력을 받을 때 반대로 받아야 Indegree의 값에 혼란이 오지 않는다. 그래야 위상정렬이 가능.

풀이

1. List를 이용하여 값을 저장해준다.(ArrayList, LinkedList 둘다 사용 가능) 

2. indegree가 0인 값을 큐에 모두 집어 넣는다.

3. 큐가 빌때까지 0인 값을 하나씩 빼서 그 다음 값을 다시 큐에 집어 넣는다. (단 그때 화살표 값인 Indegree를 하나씩 줄인다.)

4. 큐에서 빼고 난 후에 자기 자신까지 가장 오래 걸린 시간을 배열에 저장해야한다. (이전 건물들을 모두 지어야 자기 건물을 지을 수 있기 때문)

4. 끝

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        ArrayList<Integer>[] list = new ArrayList[N + 1];
        int[] indegree = new int[N + 1];
        int[] value = new int[N + 1];
        int[] result = new int[N + 1];
        int temp = 0;
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= N; i++) {
            value[i] = sc.nextInt();
            temp = sc.nextInt();
            while (temp != -1) {
                //indegree를 temp가 아닌 i 값으로 받아야한다.
                indegree[i]++;
                //리스트에 저장 될 temp 와 i 값도 바껴야 한다.
                list[temp].add(i);
                temp = sc.nextInt();
            }
        }
        
        //-----------입력 칸---------------------
        
        
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
                result[i] = value[i];
 
            }
        }
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                indegree[next]--;
                //자신의 건물을 짓기전 이전에 가장 오랜 시간 걸린 값을 찾아야 한다. 그래야 자신의 건물을 올리지
                result[next] = Math.max(result[next], result[current] + value[next]);
                System.out.println(next);
 
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
 
        }
        for (int i = 1; i <= N; i++) {
            System.out.println(result[i]);
        }
    }
}