[BaekJoon] 1516 게임 개발 (Java)

1.  문제 링크

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

2.  문제

요약

• 전략 시뮬레이션 게임 세준 크래프트의 핵심 부분은 개발이 끝난 생타고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있습니다.
• 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였습니다.
• 어떤 건물은 그 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있습니다.
• 여러 개의 건물을 동시에 지을 수 있습니다.
• 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정합니다.
• N개의 각 건물이 완성되기까지 걸리는 최소 시간을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 500보다 작거나 같은 건물의 종류 수 N이 주어지고 두 번째 줄부터 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어집니다. 각 줄은 -1로 끝납니다.
  • 건물의 번호는 1부터 N까지입니다.
  • 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수입니다.
  • 모든 건물을 짓는 것이 가능한 입력만 주어집니다.
• 출력: N개의 줄에 N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[] related, time;
	static HashMap<Integer, ArrayList<Integer>> map;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		related = new int[N + 1];
		time = new int[N + 1];
		map = new HashMap<>();
		for(int build = 1; build <= N; build++) map.put(build, new ArrayList<>());
		for(int build = 1; build <= N; build++) {
			int t = scanner.nextInt();
			int relatedNum = 0;
			int neighbor = 0;
			while(true) {
				neighbor = scanner.nextInt();
				if(neighbor == -1) break;
				map.get(neighbor).add(build);
				relatedNum++;
			}
			time[build] = t;
			related[build] = relatedNum;
 		}
	}
	
	static void solution() {
		Queue<Integer> queue = new LinkedList<>();
		int[] eachTime = new int[time.length];
		for(int build = 1; build <= N; build++) {
			eachTime[build] = time[build];
			if(related[build] == 0) queue.offer(build);
		}
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			for(int following : map.get(cur)) {
				related[following]--;
				eachTime[following] = Math.max(eachTime[following], eachTime[cur] + time[following]);
				if(related[following] == 0) queue.offer(following);
			}
		}
		for(int build = 1; build <= N; build++) sb.append(eachTime[build]).append('\n');
		System.out.println(sb);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}