[JAVA] 백준 1516 위상 정렬

 

 

 

 

1516번: 게임 개발

문제

여러개의 건물이 있을 때 각 건물은 다른 건물이 지어져야 하는 요구사항이 있다.

N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

풀이

이 문제는 건물이 앞에있는 건물들이 지어졌을 때, 지을 수 있는 건물들이 있다.

따라서 위상정렬을 통해 노드들을 제거해나가면서 시간을 계산하면 된다.

📌 입력

      ArrayList<Integer>[] A = new ArrayList[N];
      int[] D = new int[N];
      int[] time = new int[N];
        int[] answer = new int[N];

      for(int i=1; i<N; i++){
          A[i] = new ArrayList<>();
          D[i] = 0;
          time[i] = 0;
          answer[i] = 0;
      }

      for(int i=1; i<N; i++){
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
          time[i] = Integer.parseInt(st.nextToken());

          while (true){
              int pre = Integer.parseInt(st.nextToken());
              if(pre == -1) break;
              A[pre].add(i);
              D[i]++;
          }
      }

A : 그래프를 연결 리스트 형태로 구현 (B를 짓기위한 건물이 A라고 했을 때 A → B 형태로 그래프를 그렸다.)

D : 위상 정렬을 하기 위해 노드 자신에게 들어오는 화살표 즉, 건물을 짓는데 필요한 건물들을 나타내기 위해 사용 (만약 이 값이 0이라면 건물을 짓기 위한 선행 건물이 이미 완료되었다는 의미)

time : 각 건물들의 건축 시간을 담아둔다.

answer : 위상 정렬을 통해 답을 계산한다.

📌 위상 정렬

      for(int i=1; i<N; i++){
          int now = 0;
          for(int j=1; j<N; j++){
              if(D[j] == 0){
                  now = j;
                  D[j] = -1;
                  break;
              }
          }
          for (int x : A[now]){
              D[x]--;
              answer[x] = Math.max(answer[x], time[now] + answer[now]);
          }
      }

위상 정렬이다.

D 배열의 요소 중 0인 인덱스를 가져와서 A에 담겨있는 노드들을 돌면서 시간을 갱신한다.

answer[x] = Math.max(answer[x], time[now] + answer[now]);

위의 위상 정렬을 구현하면서 이부분이 정말 이해가 어려웠다.

만약 A → B, A → C, B → C이고 B → D 일때 C와 B는 똑같이 A + B의 시간을 더해서 자신에 시간에 추가해야 하지만 그냥 위상 정렬로 덧셈연산을 진행하면 C는 (A + B) + B가 되버렸다.

이를 해결하기 위해서 A → C일때 answer[C]에는 answer[C]와 time[A] + answer[now] 값 중 더 큰값을 추가하면 해결이 가능했다.

즉 C를 짓기 위해 선행되어야 하는 건물이 A, B일때 A, B의 시간을 모두 더하는 것이 아닌 A를 짓고 난 후 B를 지을 때 B에 저장된 값(A를 먼저 짓고 B를 짓는 시간)과 비교하여 더 큰값을 넣어줌으로써 (A + B) + A를 방지할 수 있었다.

📌 출력

      StringBuilder sb = new StringBuilder();
      for(int i=1; i<N; i++){
          sb.append(answer[i] + time[i]).append("\n");
      }
       System.out.println(sb);

건물을 짓기 위한 시간에 자신의 건물을 짓는 시간을 더해서 답을 구해주었다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

      int N = Integer.parseInt(br.readLine())+1;

      ArrayList<Integer>[] A = new ArrayList[N];
      int[] D = new int[N];
      int[] time = new int[N];
        int[] answer = new int[N];

      for(int i=1; i<N; i++){
          A[i] = new ArrayList<>();
          D[i] = 0;
          time[i] = 0;
          answer[i] = 0;
      }

      for(int i=1; i<N; i++){
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
          time[i] = Integer.parseInt(st.nextToken());

          while (true){
              int pre = Integer.parseInt(st.nextToken());
              if(pre == -1) break;
              A[pre].add(i);
              D[i]++;
          }
      }

      for(int i=1; i<N; i++){
          int now = 0;
          for(int j=1; j<N; j++){
              if(D[j] == 0){
                  now = j;
                  D[j] = -1;
                  break;
              }
          }
          for (int x : A[now]){
              D[x]--;
              answer[x] = Math.max(answer[x], time[now] + answer[now]);
          }
      }

      StringBuilder sb = new StringBuilder();
      for(int i=1; i<N; i++){
          sb.append(answer[i] + time[i]).append("\n");
      }
       System.out.println(sb);

    }
}

결과