[백준] 1516번 '게임 개발' - Java

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

1516번: 게임 개발

---

문제

---

코드

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int n;
	private static int[] indegree;
	
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(bf.readLine());
		indegree = new int[n + 1];
		
		ArrayList<Integer>[] graph = new ArrayList[n + 1];
		for(int i = 1 ; i <= n ; i++) {
			graph[i] = new ArrayList<>();
		}
		
		PriorityQueue<Integer> Q = new PriorityQueue<>();
		
		StringTokenizer st;
		int[] time = new int[n + 1];
		int[] ans = new int[n + 1];
		for(int i = 1 ; i <= n ; i++) {
			st = new StringTokenizer(bf.readLine());
			
			time[i] = Integer.parseInt(st.nextToken());
			
			while(true) {
				int tmp = Integer.parseInt(st.nextToken());
				if(tmp == -1) {
					if(indegree[i] == 0) {
						ans[i] = time[i];
						Q.offer(i);
					}
					break;
				}
				else {
					graph[tmp].add(i);
					indegree[i]++;
				}
			}
		}
		
		while(!Q.isEmpty()) {
			int front = Q.poll();
			for(int next : graph[front]) {
				indegree[next]--;
				ans[next] = Math.max(ans[next], time[next] + ans[front]);
				if(indegree[next] == 0) {
					Q.offer(next);
				}
			}
		}
		for(int i = 1 ; i <= n ; i++) {
			bw.write(ans[i] + "\n");
		}
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

위상 정렬을 이용하여 풀었습니다. 그래프에서 화살표의 방향은 이전에 만들어야 하는 건물 -> 만들 건물 로 갑니다.

 

큐를 이용하여 위상 정렬을 수행한다면, 진입차수가 없는(화살표를 받지 않는) 1이 큐에 먼저 들어갑니다.

1이 빠지면 1의 화살표가 향한 2에서 진입차수를 하나 빼주어 0이 됨을 확인 한 후에 2를 큐에 넣고, 3도 집입차수에서 하나를 뺀 값이 0이 됨을 확인하여 큐에 넣습니다. 하지만 4는 진입차수에 하나를 빼면 1이므로 큐에 넣지 않고 다음 수행을 진행합니다. 참고로 큐에 넣고 빼는 작업과 동시에 ans 배열을 채워줍니다.

ans[next] = Math.max(ans[next], time[next] + ans[front]);

위 코드는 ans배열을 채우는 코드입니다. 먼저 지어야 하는 건물이 여러 채 있을 경우에 가장 오래걸리는 것을 더해줘야합니다.

그 다음은 2가 향한 화살표를 확인하는데 화살표가 없으니 그냥 뺍니다. 3은 4와 5를 확인하고 4의 진입차수에 1을 한번 더 빼서 0이 되니 4를 큐에 넣습니다. 5도 진입차수 1에 1을 빼니 0이 되므로 큐에 넣습니다.

마지막 수행까지 하면 이렇게 되겠네요.

---

Search

https://freedeveloper.tistory.com/390