백준 JAVA11 1516번 : 게임 개발

Mention : topology sort

• 어떤 건물을 짓기 위해 먼저 지어야하는 건물이 있을 수 있다.
• 건물 : 노드
• 그래프 형태에서 노드 순서를 정렬한다.
• 진입 차수가 빠질때 소요 시간을 업데이트 해준다.

게임 개발

시간 제한	메모리 제한
2 초	128 MB

문제

숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

입력

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. 모든 건물을 짓는 것이 가능한 입력만 주어진다.

출력

N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

예제 입력 1

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

예제 출력 1

10
20
14
18
17

반례 Input
4
1 4 3 2 -1
2 4 -1
1 4 -1
1 -1
반례 Output
4
3
2
1

출처

• 빠진 조건을 찾은 사람: jung2381187, vl0612
• 데이터를 추가한 사람: lch9502

슈도 코드

N(건물의 수)
ArrayList<>[]A (데이터 저장 인접 리스트)
inDegree(진입차수 배열)
dTime(각 건물의 소요 건설시간 배열)
result(결과 리스트)
for(N+1만큼) {
	인접 리스트 초기화
}
for(N+1만큼) {
	dTime 데이터 저장
	while(!= -1) {
	A 그래프 데이터 저장
	inDegree++ (데이터 저장시 진입차수 ++)
	}
}
큐 자료구조
for(N만큼) {
	if(inDegree[i] == 0) {
	큐에 데이터를 넣어준다.
	}
}
while(큐에 데이터가 없을때까지 반복) {
	큐에서 데이터를 빼준다.
	for(큐에서 빼낸 데이터의 갯수만큼)
		해당 노드의 연결 데이터들을 D--
		result = dTime 배열을 대조 및 합산해서 업데이트 
		if(D[i] == 0)
		큐에 데이터를 넣어준다.
}
for(N만큼){
완성된 건물별 이전테크트리를 거치는 소요시간 + 자기건물을 짓는시간 
출력
}

Code.

package graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P1516_game {
	static ArrayList<Integer>[] A;
	static int[] inDegree;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[] durationOfTime = new int[N + 1];
		int[] result = new int[N+1];
		A = new ArrayList[N + 1];
		inDegree = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			A[i] = new ArrayList<>();
		}
		
		int k = 1;
		while (k != N + 1) {
			int j = 1;
			durationOfTime[k] = sc.nextInt();
			while (k <= N) {
				int x = sc.nextInt();
				if (x == -1) {
					j++;
					break;
				}
				A[x].add(k);
				inDegree[k]++;
				j++;
			}
			k++;
		}

		Queue<Integer> queue = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				queue.offer(i);
			}
		}
		while (!queue.isEmpty()) {
			int now = queue.poll();
			for (int next : A[now]) {
				inDegree[next]--;
				result[next] = Math.max(result[next], result[now] + durationOfTime[now]);
				if (inDegree[next] == 0) {
					queue.offer(next);
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			System.out.println(result[i] + durationOfTime[i]);
		}
	}

}