- 생각
1. 배열을 만들어서 지어도 되는 건물 index를 먼저 채워 넣으며 다른 건물을 더 해준다. 이걸 어떻게 구현해야 될 지 찾아보니 이런 상황에서 풀 때 쓰면 좋은 알고리즘을 찾았다. 위상 정렬이라는 알고리즘이다.
위상 정렬 (velog.io/@max9106/Algorithm-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-Sort - 직접 정리해서 링크 바꿔 놓자!)
- 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
- DAG(Directed Acyclic Graph: 사이클이 존재하지 않는 방향 그래프)에만 적용할 수 있다.
- 코드
정답 코드 : 위상 정렬을 큐를 사용하여 구현한 코드이다. 위상 정렬을 처음 접해 보았는데 코드가 깔끔하다.
import java.io.BufferedReader;
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 {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> preBuildingNumber = new ArrayList<>();
for (int i = 0; i <= N; i++) {
preBuildingNumber.add(new ArrayList<>());
}
int[] indegree = new int[N + 1]; // 특정 건물을 짓기 전에 먼저 지어야 할 건물의 개수
int[] times = new int[N + 1]; // 특정 건물을 짓는 데 걸리는 시간
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
times[i] = Integer.parseInt(st.nextToken()); // 해당 건물을 짓기 위한 시간
while (true) {
int preBuildingNumberTemp = Integer.parseInt(st.nextToken());
if (preBuildingNumberTemp == -1)
break;
preBuildingNumber.get(preBuildingNumberTemp).add(i);
indegree[i]++; // 해당 건물을 짓기 전 지어야 할 건물의 수를 더해준다.
}
}
String timeForBuilding = topologicalSort(preBuildingNumber, indegree, times, N);
System.out.print(timeForBuilding);
}
// 위상 정렬
public static String topologicalSort(ArrayList<ArrayList<Integer>> a, int[] indegree, int[] times, int N) {
Queue<Integer> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
// 먼저 지어야할 건물이 없는 건물을 큐에 집어 넣음. 해당 큐에 있는 건물을 먼저 짓는다.
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
// 특정 건물을 짓기 전까지 걸린 시간 누적
int[] result = new int[N + 1];
while (!queue.isEmpty()) {
int now = queue.poll();
for (int next : a.get(now)) {
indegree[next]--;
// indegree를 줄여나가는 과정
// result[next] = max(result[next], result[now] + times[now])
// 위의 수식을 활용하여 result의 값을 초기화하는 것이 핵심
result[next] = Math.max(result[next], result[now] + times[now]);
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
// 특정 건물을 짓기 전 먼저 지어야할 건물의 시간 + 특정 건물을 짓는 시간
for (int i = 1; i <= N; i++) {
sb.append((result[i] + times[i]) + "\n");
}
return sb.toString();
}
}
'algorithm' 카테고리의 다른 글
[JAVA] 백준 2011번 : 암호코드 (0) | 2020.11.05 |
---|---|
[JAVA] 백준 1062번 : 가르침 (0) | 2020.11.04 |
[JAVA] 백준 9507번 : Generations of Tribbles (0) | 2020.11.02 |
[JAVA] 백준 1937번 : 욕심쟁이 판다 (0) | 2020.11.02 |
[JAVA] 백준 1965번 : 상자넣기 (0) | 2020.10.26 |