[Java] BOJ 1005 - ACM Craft

 

 

BOJ 1005 - ACM Craft (https://www.acmicpc.net/problem/1005)

 

01. 🔎 문제 탐색

• 매 게임시작 시 건물을 짓는 순서가 주어짐
  (각 게임마다 건물을 짓는 순서가 다를 수 있음)
• 모든 건물은 각각 건설을 시작
  (다음 건물은 선행 건물이 모두 완성되어야 건설 시작 가능)

N: 건물의 개수
K: 건설 순서 규칙의 개수
$D_1, D_2, ..., D_N$: 1~N번 건물의 건설에 걸리는 시간
X, Y: X건물이 선행되어야 Y건물을 건설할 수 있음
W: 목표 건물

• 목표 W번 건물이 건설완료 하는데 드는 최소 시간을 출력

01-1. 알고리즘 선택 & 시간 복잡도

• 시작 건물과 건물을 짓는 순서가 게임마다 바뀌므로, 위상 정렬을 이용하여 주어지는 건설 순서로 탐색을 진행
• 이전 건물 건설에 걸린 최대 시간이 다음 건물 건설 시작 시작에 영향을 받으므로, DP를 이용하여 이를 구현

02. 📝 코드 설계하기

1. 건물에 대한 정보(건설 시간, 건물 순서, 목표 건물)를 입력
2. X 다음에 올 Y를 2차원 배열로 저장
3. Y에 자주 입력되는 건물일 수록, 나중에 건설되므로 집입 차수를 Y에 대해 진입 차수를 +1씩 해줌
4. 진입차수가 0인 건물을 Queue에 담음
5. Queue에서 요소를 하나 씩 꺼내며 반복
6. 꺼낸 요소에 대해 다음 순서의 건물을 탐색
   1. 현재 건물 건설에 걸린 시간 time[i]와 다음 건물 건설 시간 D[i+1]을 더한 값과 time[i+1]을 비교하여 더 큰 값을 time[i+1]로 함
   2. 다음 건물의 진입 차수를 -1 하고 진입 차수가 0이 되면, 선행 건물들이 모두 완료되었다는 것으로 Queue에 추가
7. 각 건물에 대한 최대값이 time[i]에 저장되어 있으므로, time[W]를 출력

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

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

public class boj1005 {
  static int T;
  static int N, K, W;
  static int X, Y;
  static int[] D;
  static List<Integer>[] graph;
  static int[] indegree;
  static int[] time;

  public static int solution(){
    Queue<Integer> q = new LinkedList<>();
    time = new int[1_001];

    for(int i = 1; i <= N; i++){
      if(indegree[i] == 0) {
        q.offer(i);
        time[i] = D[i];
      }
    }

    while(!q.isEmpty()){
      int cur = q.poll();
      for(int i = 0; i < graph[cur].size(); i++){
        int nxt = graph[cur].get(i);

        indegree[nxt]--;

        time[nxt] = Math.max(time[cur] + D[nxt], time[nxt]);
        
        if(indegree[nxt] == 0) q.offer(nxt);
      }
    }

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

    T = Integer.valueOf(br.readLine());
    D = new int[1_001];
    graph = new ArrayList[1_001];

    while(T-- > 0){
      st = new StringTokenizer(br.readLine());
      N = Integer.valueOf(st.nextToken());
      K = Integer.valueOf(st.nextToken());

      st = new StringTokenizer(br.readLine());
      for(int i = 1; i <= N; i++) D[i] = Integer.valueOf(st.nextToken());

      for(int i = 0; i < 1001; i++) graph[i] = new ArrayList<Integer>();
      indegree = new int[1001];
      for(int i = 1; i <= K; i++){
        st = new StringTokenizer(br.readLine());
        X = Integer.valueOf(st.nextToken());
        Y = Integer.valueOf(st.nextToken());

        graph[X].add(Y);
        indegree[Y]++;
      }
      W = Integer.valueOf(br.readLine());

      bw.write(solution() + "\n");
    }

    bw.flush();
    bw.close();
    br.close();
  }
}