위상정렬을 이용해 풀 수 있는 문제
건물을 짓기 위해 다른 건물을 먼저 지어야 하는 경우가 있다고 했기 때문에,
가장 처음에 지을 수 있는 건물(indegree가 0인 건물) 부터 지을 수 있다.
그래서, 위상정렬을 이용하면 쉽게 풀리는 문제
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
//System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> list[] = new ArrayList[N+1];
for(int i=1; i<=N; i++) {
list[i] = new ArrayList<Integer>();
}
int indegree[] = new int[N+1];
int building_time[] = new int[N+1];
int prebuilding;
for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
building_time[i] = Integer.parseInt(st.nextToken());
prebuilding = Integer.parseInt(st.nextToken());
while(prebuilding != -1) {
list[prebuilding].add(i);
indegree[i]++;
prebuilding = Integer.parseInt(st.nextToken());
}
}
int elapsed_time[] = new int[N+1];
// Queue 초기값 (indegree = 0)
Queue<Integer> q = new LinkedList<Integer>();
for(int i=1; i<=N; i++) {
if(indegree[i] == 0) {
q.add(i);
elapsed_time[i] = building_time[i];
}
}
// START
int now_building;
while(!q.isEmpty()) {
now_building = q.poll();
for(int next_building : list[now_building]) {
indegree[next_building]--;
elapsed_time[next_building] = Math.max(elapsed_time[next_building], elapsed_time[now_building] + building_time[next_building]);
if(indegree[next_building] == 0) {
q.add(next_building);
}
}
}
for(int i=1; i<=N; i++) {
System.out.println(elapsed_time[i]);
}
}
}
댓글