[백준/Java] 1516 게임 개발

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

문제 요약

N개의 줄에는 각 건물을 짓는 시간과 그 건물을 짓는 데 필요한 건물이 주어진다. 각 줄은 -1로 끝난다.
건물의 번호는 순서대로 1부터 N이라고 하자.
N개의 각 건물이 지어지는데 필요한 최소 시간을 모두 구하자.
이때 N은 최대 500이며, 각 건물을 짓는데 필요한 시간은 최대 10만이다.

---

문제 접근

위상 정렬을 활용해서 해결할 수 있는 문제이다.
각 건물을 짓는데 필요한 시간을 기록하는 배열을 만들어서, 필요한 건물이 지어진 가장 긴 시간을 더해주면 된다.
필요한 건물의 개수를 기록하는 배열, 내가 가리키는 건물의 리스트 사용
해당 건물을 짓는데 필요한 시간의 배열도 사용
숫자 번호가 1부터 시작하기 때문에 크기는 N+1로, 인덱스는 1부터 N까지 사용
위상 정렬을 수행할 때는 큐 사용

---

풀이

기본적인 아이디어는 다음과 같다.

1. (추가 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	static int N;
	
	static int[] numNeedBuilding;
	static ArrayList<Integer>[] nextBuilding;
	
	static int[] oneConstTime;
	static int[] totalConstTime;
	
	static StringBuilder answer = new StringBuilder();
	
	// 입력 받기
	public static void getInput() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		numNeedBuilding = new int[N+1];
		nextBuilding = new ArrayList[N+1];
		for (int i = 0; i < N+1; i++) {
			nextBuilding[i] = new ArrayList<>();
		}
		
		oneConstTime = new int[N+1];
		totalConstTime = new int[N+1];
		
		// i+1번째 건물에 대한 정보 얻기
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			// 해당 건물 하나를 짓는데 필요한 시간(oneConstTime) 기록
			int constTime = Integer.parseInt(st.nextToken());
			oneConstTime[i+1] = constTime;
			
			// 짓는데 필요한 건물 개수(numNeedBuilding)와 해당 건물이 있어야 지을 수 있는 건물(nextBuilding) 기록
			int count = 0;
			int needBuilding = Integer.parseInt(st.nextToken());
			while (needBuilding > 0) {
				count++;
				nextBuilding[needBuilding].add(i+1);
				needBuilding = Integer.parseInt(st.nextToken());
			}
			numNeedBuilding[i+1] = count;
		}
		
		// 각 건물의 필요한 총 시간을 기록하는 배열(totalConstTime) 초기화
		for (int i = 0; i < N+1; i++) {
			totalConstTime[i] = 0;
		}
	}
	
	public static void calLeastConstTime() {
		ArrayDeque<Integer> que = new ArrayDeque<>();
		
		// 필요한 건물이 없는 건물들을 큐에 추가
		for (int i = 1; i < N+1; i++) {
			if (numNeedBuilding[i] == 0) {
				que.add(i);
			}
		}
		
		// 큐가 빌 때까지 반복
		while (que.size() > 0) {
			int now = que.poll();
			
			// 현재 건물의 최소 시간 구하기
			totalConstTime[now] += oneConstTime[now];
			
			// 해당 건물을 필요로 하는 건물들의 개수 줄여주기
			// 만약 그 개수가 0이 된다면 큐에 추가해줌
			// 동시에 필요한 시간도 갱신해줌
			for (int next : nextBuilding[now]) {
				numNeedBuilding[next]--;
				
				if (numNeedBuilding[next] == 0) {
					que.add(next);
				}
				
				totalConstTime[next] = Math.max(totalConstTime[next], totalConstTime[now]);
			}
		}
	}
	
	public static void makeAnswer() {
		for (int i = 1; i < N+1; i++) {
			answer.append(totalConstTime[i]+"\n");
		}
		
		System.out.println(answer);
	}
    
    public static void main(String[] args) throws IOException {
        // 입력 받기
        getInput();
        
        // 위상 정렬을 이용해 정답 얻기
        calLeastConstTime();
        
        // 정답 구성 및 출력
        makeAnswer();
    }
}

---

회고

(추가 예정)