[백준] 1516 게임 개발 - JAVA

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

 

 

알고리즘

• "어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에"
• 순서가 정해져 있는 작업을 차례로 수행할 때 순서를 결정하기 위한 알고리즘 : 위상정렬을 사용하여 접근 
• 단, 여러개의 건물이 동시에 지어질 수 있는 경우를 고려하여 시간을 계산해야 한다. 

 

💡예를 들어, C 건물을 짓기 위해서는 A와 B 건물이 지어져야 한다고 가정해보자. 

A 건물이 10초, B 건물이 20초 걸린다면 C 건물은 20초 후에 지을 수 있다. A,B는 동시에 건설할 수 있기 때문에 더 긴 시간인 20초를 기다려야 한다. 

---

 

구현 과정

• List<List> list : 그래프 구현을 위한 인접리스트 
• inCnt[] : 각 건물을 짓기 전에 먼저 지어야 하는 건물의 갯수 
• time[] : 각 건물을 짓는데 걸리는 시간 
• pre_time[] : 각 건물을 지을 수 있을 때 까지 걸리는 시간 
• 즉, 건물을 완성하는데 필요한 총 시간 = pre_time[i] + time[i] 

 

1. 주어진 입력정보를 이용하여 list, inCnt, time 값을 채우고 만약 inCnt[i] = 0 즉, 먼저 지어야 할 건물이 없는 경우 큐에 넣는다. 

 

2. 큐에서 하나씩 꺼내며 큐가 빌 때까지 아래 과정을 반복한다. 

 

3. 현재 건물과 그래프 상 연결되어 있는 건물 (= 현재 건물을 짓고 나면 지을 수 있는 다음 건물(들))의 inCnt를 1 줄인다. 

 

4. 현재 건물을 짓기까지 걸린 시간 + 현재 건물을 짓는데 걸린 시간 vs 다음 건물을 짓기 전까지 걸린 시간 중 더 큰 값을 pre_time 에 저장한다. 

 

5. 만약 다음 건물의 inCnt 값이 0이라면 즉, 먼저 지어야 하는 건물을 다 지었다면, 큐에 넣는다. 

 

6. 최종적으로 모든 건물들의 pre_time 과 time 값을 더하여 출력한다. 

 

 

👉예제 입력 1

 

건물번호	1	2	3	4	5
list	{ 2,3,4 }		{ 4,5 }
time	10	10	4	4	3
inCnt	0	1	1	2	1
pre_time	0	0	0	0	0
que	1

• 1 이후에 지을 수 있는 건물 { 2,3,4 } 의 inCnt 값을 1씩 줄인다. 
• pre_time 값이 현재 0으로 초기화 되어 있으므로 pre_time 값을 time[1] = 10으로 바꾼다.
  즉, 현재까지 2,3,4 를 짓기 전까지 걸리는 시간 = 1을 짓는데 걸리는 시간 = 10 
• inCnt 가 0이 된 2,3 건물을 큐에 넣는다.

 

 

건물번호	1	2	3	4	5
list	{ 2,3,4 }		{ 4,5 }
time	10	10	4	4	3
inCnt	0	0	0	1	1
pre_time	0	10	10	10	0
que	2	3

• que.poll() = 2, 2와 연결된 건물이 없기 때문에 다음 
• que.poll() = 3 
• 3 이후에 지을 수 있는 건물 { 4,5 } 의 inCnt 값을 1씩 줄인다. 
• 현재 4번 건물을 짓기 전까지 걸리는 시간은 10 (=1번 건물만 완성) 으로 되어 있다. 
  하지만, 4번 건물을 짓기 위해선 1, 3 건물을 모두 지어야 한다. 3번 건물을 짓는데 걸리는 시간은 ( =1번 건물 완성 이후, 3번 건물 완성) ➡️ 10 + 4 = 14이다. 
  14와 10중 더 큰값인 14만큼 기다려야 4번 건물을 지을 수 있다. (만약 10만 기다렸다면 3번 건물은 다 완성하지 못하고 4번을 지은 것이기 때문에 ❌) 
• 5번 건물 또한 3번 건물이 완성될 때 까지 기다려야 하므로 10+4 = 14 로 pre_time 값을 변경한다. 
• 4,5 모두 isCnt 값이 0이 되었으므로 큐에 넣는다. 

 

 

건물번호	1	2	3	4	5
list	{ 2,3,4 }		{ 4,5 }
time	10	10	4	4	3
inCnt	0	0	0	0	0
pre_time	0	10	10	14	14
que	4	5

• que.poll 하여 4 , 5 를 꺼냈지만 모두 연결되어 있는 건물이 없기 때문에 종료 
• 최종적으로 건물을 완성하는데 걸리는 시간은 건물 짓기 전까지 기다린 시간 + 건물 짓는 시간으로 pre_time 과 time 을 더하여 출력하면 끝 ! 

---

 

소스 코드 

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

public class Solution_BaekJoon_1516 {
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
        
		Queue<Integer> que= new LinkedList<>();
		int N = Integer.parseInt(br.readLine()); //건물의 종류 수 
		List<ArrayList<Integer>> list= new ArrayList<>(); 
		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<>());
		}
		
		int[] time = new int[N+1];//건물을 짓는데 걸리는 시간 
		int[] inCnt = new int[N+1];//진입차수 
        
		//입력받은 값으로 연결 리스트 그래프 구현 
		for(int i=1; i<=N; i++) {
			st= new StringTokenizer(br.readLine(), " ");
			time[i] = Integer.parseInt(st.nextToken());
			while(true) {
				int j = Integer.parseInt(st.nextToken()); 
				if(j == -1) break; 
				inCnt[i]++; 
				list.get(j).add(i); 
			}
			if(inCnt[i]==0) {
				que.add(i);
			}
		}
		
		int pre_time[] = new int[N+1]; //건물을 지을 수 있을 때까지 걸리는 시간 
		while(!que.isEmpty()) {
			int now= que.poll();
			for(int i=0; i<list.get(now).size(); i++) {
				int next= list.get(now).get(i);
				inCnt[next]--;
				pre_time[next] = Math.max(pre_time[next], time[now]+pre_time[now]); 
				if(inCnt[next] == 0) {
					que.add(next);
				}
			}
		}
		
		for(int i=1; i<=N; i++) System.out.println(time[i]+pre_time[i]);
        
	}//end of main 
}