문제 조건
1. 건물을 건설하는데 순서가 존재한다.
2. 건물 건설은 동시에 가능하다
이 문제는 전형적인 위상정렬 문제이다.
아래와 같이 건물을 건설하는 데에 필요한 정보는 아래 2가지 정보이며, 예제 1에 적용해 보자
- 기다려야 하는 시간 building
- 건물을 건설하기 위해 먼저 건설해야 하는 노드의 개수 parentNum
<time=0>
<time=10>
parentNum[i] = 0인 노드부터 건설하면 된다. 큐에 넣어서 순차적으로 처리해 보자
빌딩을 건설해 주고 나면 i를 부모 노드로 하는 자식 노드들의 parentNum을 하나씩 줄여준다.
<time=110>
빌딩은 동시에 건설이 가능하기 때문에,
같은 depth의 노드들의 building 중 최댓값을 time에 더해주도록 한다.
마지막으로 최종 목표 destination node가 나타나면 바로 건설 시간을 더해준 후 리턴해준다.
풀이 코드는 아래와 같다.
import java.util.*;
public class Main {
public static int max = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int test = in.nextInt();
for (int t = 0; t < test; t++) {
int v = in.nextInt();
int e = in.nextInt();
int building[] = new int[v + 1];
for (int i = 1; i <= v; i++) {
building[i] = in.nextInt();
}
LinkedList<Integer> childs[] = new LinkedList[v + 1];
LinkedList<Integer> parents[] = new LinkedList[v + 1];
for (int i = 1; i <= v; i++) {
childs[i] = new LinkedList<Integer>();
parents[i] = new LinkedList<Integer>();
}
int[] parentNum = new int[v + 1];
for (int i = 0; i < e; i++) {
int parentNode = in.nextInt();
int childNode = in.nextInt();
childs[parentNode].add(childNode);
parents[childNode].add(parentNode);
parentNum[childNode]++;
}
int destination = in.nextInt();
System.out.println(calculateTime(destination, building, parentNum, childs, parents));
}
}
public static int calculateTime(int destination, int[] building, int[] parentNum, LinkedList<Integer> childs[],
LinkedList<Integer> parents[]) {
boolean[] isVisited = new boolean[building.length];
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 1; i < building.length; i++) {
if (parentNum[i] == 0) {
if (i == destination) { // 바로 건설 가능한 경우
return building[i];
}
queue.add(i);
}
}
while (!queue.isEmpty()) {
int now = queue.poll();
isVisited[now] = true;
for (int node : childs[now]) {
parentNum[node]--;
if (!isVisited[node] && parentNum[node] == 0) {
queue.add(node);
int max = 0;
for (int parent : parents[node]) {
max = Math.max(max, building[parent]);
}
building[node] += max;
if (node == destination) {
return building[destination];
}
}
}
}
return building[destination];
}
}
조금 어려웠던 점은 아래와 같은 반례를 생각하지 못했어서 맞왜틀을 고민했었다.
올바르게 시간을 구하기 위해서는 부모 노드들 또한 저장해야해야 했는데, 다른 스터디원들에 비해 실행 시간이 너무 오래 걸려서
한 번 생각해 봐야겠다...
'알고리즘 공부 > boj' 카테고리의 다른 글
boj 1939: 중량제한 (0) | 2021.01.20 |
---|---|
boj 17143: 낚시왕 (0) | 2021.01.20 |
boj 1949: 우수 마을 (0) | 2021.01.19 |
boj 1981: 배열에서 이동 (0) | 2021.01.17 |
boj 3745: 오름세 (0) | 2021.01.15 |