백준 1516번 : 게임 개발 java

이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다.

이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간을 더하면 됩니다.

이에 대해서 그림을 통해 설명드리도록 하겠습니다.

예제 1번의 그래프는 다음과 같은 형태입니다.

화살표의 시작점이 선행되어야 하는 정점이고 끝점이 그 후 실행 가능한 정점입니다.

이를 표로 나타내면 아래와 같습니다.

이 표에서 time은 각각의 정점을 실행하는 데에 걸리는 시간, answer은 그 정점이 실행되는 데에 총 걸리는 시간, parentNum을 선행되어야 하는 정점의 수입니다.

이제 건물을 짓기를 시작하도록 하겠습니다.

우선 처음에는 선행해야하는 건물이 없는 1번 정점을 먼저 건설합니다.

그럼 이제 1번 건물을 선행 건물로 가졌던 2와 3이 건설 가능해집니다.

4번 건물은 1번 건물을 선행 건물로 가졌지만 선행 건물로 3이 또 있기 때문에 건설 가능하지 않습니다.

처음의 표를 1번 건물을 건설했기 때문에 다음과 같이 초기화해줍니다.

answer에서 빨간색 표시는 이미 건설이 완료되었다는 의미입니다.

4번 정점은 지금 당장은 지을 수 없지만 1번 건물이 지어진 이후 지을 수 있기 때문에 무조건 10 이상의 시간이 걸립니다.

따라서 10으로 우선 초기화해줍니다.

그리고 이제 1번 건물을 지음으로써 건설 가능해진 2번 건물을 건설합니다.

이에 따라서 표도 다시 초기화해주도록 하겠습니다.

2번 건물을 건설하는 데에 10의 시간이 걸리므로 10을 더한 20이 됩니다.

이제 3번 건물을 건설하겠습니다.

이제 3번 건물을 선행 건물로 가지는 4와 5번 건물이 건설 가능해졌습니다.

3번 건물을 1번 건물 다음에 지을 수 있고 3번 건물을 짓는 데에 걸리는 시간이 4이므로 14의 시간이 걸립니다.

4와 5번 건물은 3번 건물 이후 건설 가능하므로 3번 건물을 짓는 데에 걸리는 시간으로 두 건물들을 모두 초기화해줍니다.

4번 건물을 짓는 것은 위에서 설명드린 것과 같은 방식으로 시간이 추가됩니다.

따라서 걸리는 시간은 14 + 4인 18이 됩니다.

마지막 5번 건물도 같은 과정을 거칩니다.

이제 코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static int N;
    static List<List<Integer>> l = new ArrayList<>();
    static int[] time;
    static int[] parentNum;
    static int[] answer;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        time = new int[N+1];
        parentNum = new int[N+1];
        answer = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        for(int i = 1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            time[i] = Integer.parseInt(st.nextToken());

            while(st.hasMoreTokens()){
                int num = Integer.parseInt(st.nextToken());

                if(num == -1)
                    break;

                l.get(num).add(i);
                parentNum[i]++;
            }
        }

        topologicalSort();

        for(int i = 1; i<=N; i++)
            System.out.println(answer[i]);
    }

    static void topologicalSort(){
        Queue<Integer> q = new LinkedList<>();

        for(int i = 1; i<=N; i++)
            if(parentNum[i] == 0)
                q.offer(i);

        while(!q.isEmpty()){
            int vertex = q.poll();
            answer[vertex] += time[vertex];

            for(int i = 0; i<l.get(vertex).size(); i++){
                int nextV = l.get(vertex).get(i);

                parentNum[nextV]--;
                if(parentNum[nextV] == 0)
                    q.offer(nextV);

                answer[nextV] = Math.max(answer[nextV], answer[vertex]);
            }
        }
    }
}

위에서 설명드린대로 코드를 작성하면 되는 해결하실 수 있습니다.