백준 1516번 자바

1. 문제

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

1516번: 게임 개발

 

2. 접근 방식

위상 정렬을 이용해서 구현하면 된다.

다만 예제와 달리

5
10 -1
10 1 -1
4 1 -1
4 3 2 5 -1
8 3 -1

이런 입력이 주어질 경우 while 문내에서 출력하면

5번째 건물의 누적시간이 4번째 건물의 누적시간보다 먼저 출력되므로 따로 반복문을 돌려 출력해야한다.

 

3. 구현

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

public class Main1516 {

	static int N;
	static int[] structures;
	// 건설에 걸리는 시간
	static int[] time;
	// 건설에 걸리는 누적 시간
	static int[] result;
	static List<Integer>[] nodes;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		structures = new int[N+1];
		time = new int[N+1];
		result = new int[N+1];
		nodes = new ArrayList[N+1];
		for (int i=1; i<N+1; i++) {
			nodes[i] = new ArrayList<Integer>();
		}
		StringTokenizer st;
		for (int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			// i번째 건물을 짓는데 걸리는 시간
			time[i] = Integer.parseInt(st.nextToken());
			result[i] = time[i];
			int pre = Integer.parseInt(st.nextToken());
			while (pre != -1) {
				nodes[pre].add(i);
				structures[i]++;
				pre = Integer.parseInt(st.nextToken());
			}
		}
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i=1; i<=N; i++) {
			if (structures[i] == 0) {
				q.offer(i);
			}
		}
		while (!q.isEmpty()) {
			int temp = q.poll();
			int max = 0;
			for (int node : nodes[temp]) {
				structures[node]--;
				result[node] = Math.max(time[node] + result[temp], result[node]);
				if (structures[node] == 0) {
					q.offer(node);
				}
			}
		}
		for (int i=1; i<result.length; i++) {
			System.out.println(result[i]);
		}
	}
}

 

4. 정리