[BOJ] 1005 ACM Craft - JAVA

1. 문제

1005번: ACM Craft

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

---

2. 풀이

Building 클래스

ArrayList<Integer> next	간선들의 다음 목적지를 저장
int total	현재 건물까지 도달하기 위한 시간
int enter	현재 건물에 접근하는 간선 개수

public static class Building{
   ArrayList<Integer> next = new ArrayList<>();
   int total, enter;
}

 

입력받는 부분

테스트케이스 받는 부분이나 각종 객체 선언은 생략했다.

int[] time	건물 짓는데 걸리는 시간
Building[] buildings	건물번호에 따른 건물 객체

간선을 K개 입력받으면서 buildings[from]의 next에는 to를 더한다. (간선 목적지 추가)

buildings[to]의 enter은 buildings[to]로 접근하는 간선이 하나 더 추가된 것이므로 enter+=1을 한다.

st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());

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

Building[] buildings = new Building[N+1];
for(int i=1;i<=N;i++) buildings[i] = new Building();

//from : 나가는 간선의 목적지 저장(list)
//to : 들어오는 간선 수 저장
int from, to;
for(int i=0;i<K;i++){
   st = new StringTokenizer(in.readLine());
   from = Integer.parseInt(st.nextToken());
   to = Integer.parseInt(st.nextToken());
   buildings[from].next.add(to);
   buildings[to].enter++;
}

//찾아야 하는 건물번호
W = Integer.parseInt(in.readLine());

 

BFS

1.  큐의 초기값으로 enter이 0인 건물번호를 넣는다. 이때, 그 건물의 total값을 time[i]로 바꾸고, enter은 방문처리 대신으로 사용하도록 -1로 바꾼다.

2.  큐에서 뽑은 값이 W와 동일하다면 answer에 total값을 넣고 끝낸다.

3.  now에서 나가는 간선을 하나씩 탐색한다.(=next 탐색)

3-1.  next의 한 요소를 n이라고 할 때, n의 total값은 Math.max(n의 total값, now의 total값)을 저장한다. 이전 건물이 모두 지어진 다음에 next를 건설할 수 있기 때문이다.

3-2.  n으로 들어오는 간선이 하나 줄었기 때문에 n의 enter에서 1을 뺀다. 

3-3.  enter이 0이라면 n은 더이상 미리 지어야 하는 건물이 없는 것이다. 큐에 n을 더하고, total에 n번째 건물 짓는 시간을 추가한다. enter도 -1로 변경한다.

4.  answer을 sb에 더한다.

//들어오는 간선 0인 걸 큐에 넣기
Queue<Integer> queue = new ArrayDeque<>();
for(int i=1;i<=N;i++) {
   if(buildings[i].enter==0) {
      queue.offer(i);
      buildings[i].total = time[i];
      buildings[i].enter = -1;
   }
}

int now;
int answer = 0;
while(!queue.isEmpty()){
   now = queue.poll();
   if(now==W){
      answer = buildings[now].total;
      break;
   }

   //나가는 간선 리스트 하나씩 탐색
   for(int n:buildings[now].next){
      buildings[n].total = Math.max(buildings[n].total, buildings[now].total);
      buildings[n].enter-=1;
      if(buildings[n].enter==0){
         queue.offer(n);
         buildings[n].total += time[n];
         buildings[n].enter = -1;
      }
   }

}
sb.append(answer).append('\n');

 

전체 코드

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

public class BOJ_1005_ACMCraft2 {
   public static class Building{
      ArrayList<Integer> next = new ArrayList<>();
      int total, enter;
   }
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      StringTokenizer st;
      int N,K,W;
      int[] time;
      for(int tc=0;tc<T;tc++){
         st = new StringTokenizer(in.readLine());
         N = Integer.parseInt(st.nextToken());
         K = Integer.parseInt(st.nextToken());

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

         Building[] buildings = new Building[N+1];
         for(int i=1;i<=N;i++) buildings[i] = new Building();

         //from : 나가는 간선의 목적지 저장(list)
         //to : 들어오는 간선 수 저장
         int from, to;
         for(int i=0;i<K;i++){
            st = new StringTokenizer(in.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            buildings[from].next.add(to);
            buildings[to].enter++;
         }

         //찾아야 하는 건물번호
         W = Integer.parseInt(in.readLine());

         //들어오는 간선 0인 걸 큐에 넣기
         Queue<Integer> queue = new ArrayDeque<>();
         for(int i=1;i<=N;i++) {
            if(buildings[i].enter==0) {
               queue.offer(i);
               buildings[i].total = time[i];
               buildings[i].enter = -1;
            }
         }

         int now;
         int answer = 0;
         while(!queue.isEmpty()){
            now = queue.poll();
            if(now==W){
               answer = buildings[now].total;
               break;
            }

            //나가는 간선 리스트 하나씩 탐색
            //n의 total값은 n의 total값과 now의 total값 중 최대값으로 저장
            //enter-1하고, 그 값이 0이라면 n은 더 이상 앞에서 체크해야 하는 간선이 없는 것
            //더이상 체크해야하는 간선이 없다면 큐에 더하고, total에 n번 건물 짓는 시간을 추가함
            //enter을 -1로 바꿔서 방문처리를 대신함
            for(int n:buildings[now].next){
               buildings[n].total = Math.max(buildings[n].total, buildings[now].total);
               buildings[n].enter-=1;
               if(buildings[n].enter==0){
                  queue.offer(n);
                  buildings[n].total += time[n];
                  buildings[n].enter = -1;
               }
            }

         }
         sb.append(answer).append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과

class를 만들어서 따로 모았더니 시간이 줄고 코드 가독성도 좋아졌다. 로직이 비슷한만큼 메모리도 비슷하다.