백준 1516 게임 개발 (Java)

1. 문제 링크

1516번: 게임 개발

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 위상정렬을 이용해서 푸는 문제이다.
2. 진입 차수를 이용해서 큐에 넣는 타이밍을 정한다.
3. dp를 이용해 더 큰 경우를 저장한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static class Building {
		int num;
		Building link;

		public Building(int num, Building link) {
			super();
			this.num = num;
			this.link = link;
		}
	}

	static int N, time[], in[], dp[];
	static Building[] list;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		list = new Building[N + 1]; // 1번부터 쓰려고
		time = new int[N + 1]; 
		in = new int[N + 1]; //진입 차수
		dp = new int[N + 1];
		for (int i = 1; i < N+1; i++) {
			String[] split = br.readLine().split(" ");
			int num = Integer.parseInt(split[0]);
			if (split.length > 2) {
				for (int j = 1; j < split.length - 1; j++) {
					int next = Integer.parseInt(split[j]);
					list[next] = new Building(i, list[next]);
					in[i]++;
				}
			}
			time[i] = num;
		}

		topology();
		for(int i=1; i<N+1;i++) {
			sb.append(dp[i]).append("\n");
		}
		System.out.println(sb);
	}

	//위상 정렬
	private static void topology() {
		Queue<Integer> queue = new ArrayDeque<>();
		for (int i = 1; i < N + 1; i++) {
			if (in[i] == 0) { //진입차수가 0인 경우만 큐에 넣기
				dp[i] = time[i];
				queue.offer(i);
			}
		}

		while (!queue.isEmpty()) {
			int current = queue.poll();
			for (Building temp = list[current]; temp != null; temp = temp.link) {
				int now = temp.num;
				dp[now] = Math.max(dp[current] + time[now], dp[now]);
				if (--in[now] == 0) {
					queue.offer(now);
				}
			}
		}
	}
}