[백준] 게임 개발 1516 - JAVA

문제

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

1516번: 게임 개발

 

풀이

스타크래프트처럼 건물을 짓는데 순서가 있다. 따라서, 위상정렬을 이용하여 풀면된다.

자세한 내용은 바킹독님의 강의에 잘 나와있으니 밑 링크를 참고하면 되겠다

https://blog.encrypted.gg/1020

 

위상정렬을 이용할때에는 그래프를 저장하기위한 인접리스트와 indegree 배열이 필요하다.

이 문제에서는 각 건물을 짓는데 걸리는 시간을 구하기 때문에 이를 저장할 배열 선언도 필요하다.

 

각 건물을 짓는데 걸리는 시간은 이전의 건물을 짓는데 걸리는 최대시간에 현재 건물을 짓는데 걸리는 시간을 합하면 된다.

 

코드

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

public class Main {	 
	
	static int n;
	static ArrayList<Integer> arr[];
	static int indegree[];
	static int distance [];
	static int result [];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n+1];
		indegree = new int [n+1];
		distance = new int [n+1];
		result = new int [n+1];
		
		Queue<Integer> que = new LinkedList<>();
		
		for(int i=1;i<=n;i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			int dist = Integer.parseInt(st.nextToken());
			distance[i] = dist;
			
			String str;
			while(!(str = st.nextToken()).equals("-1")) {
				int v = Integer.parseInt(str);
				indegree[i] = indegree[i]+1;
				arr[v].add(i);
			}
		}
		
		for(int i=1;i<=n;i++) {
			if(indegree[i] == 0) {
				que.offer(i);
			}
		}
		
		while(!que.isEmpty()) {
			int cur = que.poll();
			result[cur] += distance[cur];
			
			for(int next : arr[cur]) {
				if(result[next] < result[cur])
					result[next] = result[cur];
				indegree[next] -= 1;
				if(indegree[next] == 0)
					que.offer(next);
			}
		}
		
		for(int i=1;i<=n;i++) {
			System.out.println(result[i]);
		}
	}
	

}