[1516] 게임 개발 - Java[자바]

 

 

| 문제 링크

 

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

1516번: 게임 개발

 

 

 

 

---

 

 

 

 

| 문제

 

1. 세준 크래프트에서 건물은 건설하기 위해서 선행 건물이 필요한 건물과 선행 건물 없이 건설 할 수 있는 건물 두 가지가 있습니다.
2. 모든 건물은 건설 가능하며, N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력하시오. (1 ≤ N ≤ 500)

 

 

 

 

---

 

 

 

| 풀이

 

1. 위상정렬로 풀이했으며, 우선 건물 별 다음으로 지을 수 있는 건물들을 인접리스트로 구현 & 각 건물 별 선행적으로 지어져야하는 건물의 개수(degree)를 배열 구현합니다.
2. 건물 별 건설하는데 걸리는 시간이 담긴 배열 & 건물 별 해당 건물이 지어지지 까지 선행 건물들의 시간을 누적한 배열을 구현합니다.
3. 선행 건물이 필요 없는 건물들을 아래의 형태에 맞추어 int[] 배열 형태로 Queue에 넣습니다.
   {건물의 번호, 건설 시간}
4. Queue에서 첫 번째 배열을 추출합니다. 추출한 값의 건물 번호에 연결된 건물들의 소요되는 누적 시간의 맥스값을 갱신하고 degree를 1씩 감소시키며, degree가 0이되면(선행 적으로 지어져야하는 건물이 모두 지어짐을 의미) 해당 건물 번호와 해당 건물 까지 걸리는 누적 시간을 Queue에 넣습니다.
5. Queue가 빌 때 까지 while문으로 4번을 반복한 다음 건물별 누적 시간을 출력합니다.

 

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		//인접리스트 배열 초기화
		List<Integer>[] graph = new ArrayList[n+1];
		//선행되어야 하는 건물들의 수를 나타내는 배열 degree 초기화
		int[] degree = new int[n+1];
		//각 건물들을 건설하는데 걸리는 시간
		int[] time = new int[n+1];
		int[] timeTotal = new int[n+1];
		//위에서의 초기화는 배열을 만드는 초기화였으며
		//각 배열의 인덱스의 값은 null로 설정되어있어, 각 인덱스 별 ArrayList 초기화
		for(int i = 1; i<=n; i++) {
			graph[i] = new ArrayList<>();
		}
		//인접리스트에 값 추가
		for(int i = 1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			time[i] = t;
			timeTotal[i] = t; 
			
			while(st.hasMoreTokens()) {
				int node = Integer.parseInt(st.nextToken());
				if(node != -1) {
					degree[i]++;
					graph[node].add(i);
				}
			}
		}
		//각 건물별 연결된 건물들의 시간을 더해 맥스값을 갱신
		Queue<int[]> que = new LinkedList<>();
		for(int i = 1; i<=n; i++) {
			//선행 노드가 필요없는 노드들을 que에 넣음
			if(degree[i]==0) {
				que.add(new int[] {i,time[i]});
			}
		}
		while(!que.isEmpty()) {
			
			int[] node = que.poll();
			int nodeNum = node[0];
			int buildTime = node[1];
			for(int nextNode : graph[nodeNum]) {
				//해당 노드까지의 걸리는 시간 중 최대값이 해당 노드까지 걸리는 시간
				timeTotal[nextNode] = Math.max(timeTotal[nextNode], buildTime+time[nextNode]);
				//선행 노드가 완료된 경우에만 que에 입력
				if(--degree[nextNode]==0)
					que.add(new int[] {nextNode,timeTotal[nextNode]});
			}
		}

		//건물 별 소요 시간을 출력
		for(int i = 1; i<=n; i++) {
			sb.append(timeTotal[i]).append('\n');
		}
		
		bw.write(sb.toString());
		br.close();
		bw.close();
	}

}