[백준 1516] 게임 개발 (JAVA)

백준 1516번 문제 - 게임 개발

1516번: 게임 개발

---

문제 분석

 

• 건물을 짓기 위해 선행되어야하는 건물이 있다. 그럼 이 건물을 짓기 위해 필요한 최소 시간을 출력한다.
  • 2, 3 둘 다 1번 건물이 필요할 때 : 1번 짓고 2번 1번 또 짓고 3번이 아니라, 1번 짓고 2, 3을 짓는 것으로 시간을 잰다.

---

해결 키 포인트

 

• 위상 정렬 개념 이해
• 위상 정렬할 때, inDegree 배열에 선행되어야 할 건물 개수가 아닌 자신이 선행되어야하는 건물의 개수로 한다.
• 현재 이미 건물이 건설되었을 경우와 아닌 경우 처리해야한다.
  • if (sum[index] == 0) sum[index] = building[index]; 
  • else sum[index] = Math.max(sum[index], building[index]);
• 현재 체크하는 건물이 선행 건물인 경우, 해당 건물이 필요한 건물의 시간을 구하는 법
  • 선행 건물을 통해 짓는 경우와 직접 짓는 경우 중 더 오래 걸리는 시간을 선택해야한다.
  • sum[material] = Math.max(sum[material], sum[index] + building[material]);

---

위상 정렬

 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

 

위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 
또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용 할 수 없다.

 

알고리즘

 

1. 자신이 가르키는 에지(노드)들을 ArrayList로 제작해 구현한다.

1 ➡️ 2, 3

2 ➡️ 4, 5

3 ➡️ 4

4 ➡️ 5

5

 

2. 진입 차수 배열을 구현한다. 진입 차수는 자기 자신을 가리키는 에지의 개수이다.

1 : 0

2 : 1

3 : 1

4 : 2

5 : 2

 

3. 진입 차수 배열에서 진입차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.
0인 노드 ➡️ 1

 

4. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

1 : 0

2 : 1 - 1 : 0

3 : 1 - 1 : 0

4 : 2

5 : 2

 

---

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static ArrayList<Integer>[] lists;

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

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 변수 초기화
        lists = new ArrayList[N];
        for (int i = 0; i < N; i++)
            lists[i] = new ArrayList<>();
        int[] inDegrees = new int[N];
        int[] building = new int[N];

        // N개의 건물들을 짓는데 걸리는 시간과 필요한 자원 입력
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            building[i] = time;

            while (st.countTokens() > 1) {
                int material = Integer.parseInt(st.nextToken()) - 1;
                inDegrees[i]++;
                lists[material].add(i);
            }
        }

        int [] sum = new int[N];
        // 각 건물을 건설할 때 필요한 건설 시간 알아내기
        for (int i = 0; i < N; i++) {
            int index = getZeroDegree(inDegrees);

            // 현재 건물이 이미 건설되었을 경우에 대한 처리
            if (sum[index] == 0)
                sum[index] = building[index];
            else
                sum[index] = Math.max(sum[index], building[index]);

            ArrayList<Integer> list = lists[index];
            for(int j=0;j<list.size();j++) {
                int material = list.get(j);
                // 선행 건물을 통해 짓는 경우와 직접 짓는 경우 중 더 오래 걸리는 시간을 선택
                sum[material] = Math.max(sum[material], sum[index] + building[material]);
                inDegrees[material]--;
            }
        }

        // 각 건물을 건설할 때 필요한 건설 시간 출력
        for (int i = 0; i < N; i++) {
            bw.write(sum[i]+"\n");
        }
        bw.flush();
        bw.close();
    }

    public static int getZeroDegree(int [] inDegree) {
        int index = 0;

        for(int i=0;i<inDegree.length;i++) {
            if(inDegree[i] == 0) {
                index = i;
                break;
            }
        }
        inDegree[index]--;

        return index;
    }
}