ACM Craft

---

🔗 🔗 전체 1005번 문제

조건

---

문제

---

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft(Association of Construction Mananger Craft)가 발매되었다.

이 게임은 지금까지 나온 게임들과는 다르게 ACM Craft는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

위의 예시를 보자.

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할 수 있다. (동시에 진행이 가능하다.) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번 건물의 건설을 시작할 수 있다.

따라서 4번 건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물와 3번 건물을 동시에 건설하기 시작하면 2번은 1초 뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을 수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM Craft 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정 건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정 건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

입력

---

첫째 줄에는 테스트케이스의 갯수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다, 첫째 줄에 건물의 갯수 $N$과 건물 간의 건설순서 규칙의 총 갯수 $K$가 주어진다.(전물의 번호는 1번 부터 $N$번 까지 존재한다.)

둘째 줄에는 각 건물 당 건설에 걸리는 시간 $D$가 공백을 사이로 주어진다. 셋째 줄부터 $K + 2$줄 까지 건설순서 $X$ $Y$가 주어진다.(이는 건물 X를 지은 다음에 건물 $Y$를 짓는 것이 가능하다는 의미이다.)

마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 $W$가 주어진다.

출력

---

건물 $W$를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.
건설순서는 모든 건물이 건설 가능하도록 주어진다.

제한

---

• $2 ≤ N ≤ 1,000$
• $1 ≤ K ≤ 100,000$
• $1 ≤ X, Y, W ≤ N$
• $0 ≤ D ≤ 100,000)$ $D$는 정수

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7

• 출력

TC
1
2
120
39

예제 2

---

• 입력

TC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
5
3 2
1 2 3
3 2
2 1
1
4 3
5 5 5 5
1 2
1 3
2 3
4
5 10
100000 99999 99997 99994 99990
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2
4
4 3
1 1 1 1
1 2
3 2
1 4
4
7 8
0 0 0 0 0 0 0
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
7

• 출력

TC
1
2
3
4
5
6
5
399990
2
0

풀이

---

문제는 이해가 되는데, 이를 코딩으로 풀어내기가 어려웠던 알고리즘. 위상정렬 알고리즘에 대한 이해가 있어야한다.
문제의 경우, 스타크래프트의 건물 테크트리랑 비슷한 개념으로 접근하면 된다. 군수공장을 짓기 위해선 병영을 지어야하는 것처럼, 요구 트리가 있는 건물의 경우 해당 건물을 반드시 완료해야 하며, 하나의 건물이 여러 요구 트리를 가질 경우도 존재한다. 물론 이 경우 요구하는 건물들을 모두 건설한 뒤에 건설 가능하다. 요구하는 건물들 중 하나만 건설하면 충족되는게 아니다.

위상정렬은 순서가 정해진 작업을 수행할 때, 이 순서를 결정하는 알고리즘이다. 위상정렬은 반드시 DAG(Directed Acyclic Graph, 유향 비순환 그래프) 형태여야 한다. 즉, 순서를 도식화했을 때 반드시 시작/도착점이 존재해야 한다. 시작/도착점이 구분되지 않는 순환 형태일 경우 위상정렬을 적용할 수 없다.

위상정렬은 순서를 정하는 알고리즘이고, 순서도의 형태에 따라 여러가지의 답이 나올 수 있다. 이 문제는 최적의 답을 도출하기 위해 각 건물을 건설하는데 필요한 요구 건물과 건설 시간을 적용했다.

다음 건물을 건설하기 위해선 요구 건물을 모두 건설해야하므로 요구 건물의 건설시간이 가장 많은 건물이 다음 순서가 된다.

예시 1번의 두 번째 케이스를 예시로 하여 위상정렬을 도식화하면 위 사진과 같다.

위 표는 도식를 수치화하여 정리한 것이다.

1. 순서의 시작점(진입선이 없는 점)을 찾는다. 시작점이 여러개일 경우 시작점 중 무작위로 하나를 선택해도 무방하다. (위 예시는 시작점이 하나)

2. 시작점 1을 큐에 넣고, 시작점에 연결된 진출선을 전부 제거한다.

이 과정에서 2와 3이 새로운 시작점이 된 것을 확인할 수 있다.

1을 건설하는데 걸리는 시간은 1초.

3. 2에 대해 2번 과정을 적용한다.

4와 5의 진입선이 0이 된다. 즉, 4와 5를 건설할 수 있게 된다.

2를 건설하는데는 $10(1) + 20(2)$로 총 30초가 소요된다.

4. 3에 대해 2번 과정을 적용한다.

6의 진입선이 0이 된다. 6을 건설할 수 있게 된다.

3의 건설시간은 $10(1) + 1(3)$으로 총 11초.

5. 4에 대해 2번 과정을 적용한다.

4는 진출선이 없으므로 큐에만 추가된다.

4의 건설시간은 $10(1) + 20(2) + 5(4)$로 총 35초

6. 5에 대해 2번 과정을 적용한다.

7이 5와 6에 연결되어 있으므로, 7의 진입선은 1이 된다. 아직 7을 건설할 수 없다.

5의 건설시간은 $10(1) + 20(2) + 8(5)$로 총 38초

7. 6에 대해 2번 과정을 적용한다.

7의 진입선이 0이 된다. 7을 건설할 수 있게 된다.

6의 건설시간은 $10(1) + 1(3) + 7(6)$으로 총 18초.

8. 7에 대해 2번 과정을 적용한다.

8의 진입선이 0이 된다.

1 ~ 6까지는 요구 건물이 하나였지만, 7은 두개이다. 앞서 언급했듯이, 5와 6 중 건설시간이 더 긴 것을 기준으로 계산해야한다.

즉, 7의 건설시간은 $10(1) + 20(2) + 8(5) + 1(7)$로 총 39초

5번을 기준으로 계산하므로, 6번과 중간인 3번은 계산에서 제외된다. 만약, 3의 건설시간을 1초에서 4초로 증가시켜도 결과에 영향을 미치지 않는다. 3의 건설시간을 무시하기 때문이다. 단, 3의 건설시간이 너무 커지게되면 5보다 6의 건설시간이 같이 커지게 되어 결과에 영향을 미치게 된다.

9. 8에 대해 2번 과정을 적용한다.

문제는 7에 대한 건설시간을 요구하고 있으므로 8은 무시해도 무방하다. 8의 건설시간은 $10(1) + 20(2) + 8(5) + 1(7) + 43(8)$로 총 82초

전체 소스

---

time, matrix, link의 배열 크기가 $N + 1$이다. 별다른 이유는 아니고, 건물은 1번부터 시작하는데 배열은 0번부터 시작한다. 이러한 차이에서 오는 혼란을 방지하기 위해 건물이 총 4개면 배열의 크기를 5로(0, 1, 2, 3, 4, 5)로 지정하여 0을 제외하고 1부터 사용한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 백준 전체 1005 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/01/a1005">1005 풀이</a>
 * @since 2021.05.31 Mon 19:11:58
 */
public class Main
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		StringBuilder builder = new StringBuilder();
		
		// 케이스 갯수
		int T = scanner.nextInt();
		
		for (int i = 0; i < T; i++)
		{
			// 건물 갯수
			int N = scanner.nextInt();
			
			// 규칙(건설시간) 갯수
			int K = scanner.nextInt();
			
			// 건물별 건설시간 배열
			int[] time = new int[N + 1];
			
			// 건물별 연결여부 배열
			boolean[][] matrix = new boolean[N + 1][N + 1];
			
			// 건물별 연결 갯수 배열
			int[] link = new int[N + 1];
			
			for (int j = 1; j < N + 1; j++)
			{
				time[j] = scanner.nextInt();
			}
			
			for (int j = 0; j < K; j++)
			{
				// 하위 건물
				int X = scanner.nextInt();
				
				// 상위 건물
				int Y = scanner.nextInt();
				
				matrix[X][Y] = true;
				link[Y]++;
			}
			
			// 목표 건물
			int W = scanner.nextInt();
			
			builder.append(calcTopologicalSort(time, matrix, link)[W]).append("\n");
		}
		
		System.out.println(builder.toString());
		
		scanner.close();
	}
	
	/**
	 * 위상정렬 결과 반환 함수
	 *
	 * @param time: [int[]] 건물별 건설시간
	 * @param matrix: [boolean[][]] 건물별 연결여부
	 * @param link: [int[]] 건물별 연결 갯수
	 *
	 * @return [int[]] 건물별 종 건설시간 배열
	 */
	private static int[] calcTopologicalSort(int[] time, boolean[][] matrix, int[] link)
	{
		Queue<Integer> queue = new LinkedList<>();
		
		int[] result = new int[link.length];
		
		for (int i = 1; i < link.length; i++)
		{
			// 요구 건물이 없는 건물일 경우
			if (link[i] == 0)
			{
				result[i] = time[i];
				queue.add(i);
			}
		}
		
		while (!queue.isEmpty())
		{
			// 하위 건물
			int prev = queue.poll();
			
			for (int i = 1; i < link.length; i++)
			{
				// 하위 건물 건설을 요구 하는 건물일 경우
				if (matrix[prev][i])
				{
					result[i] = Math.max(result[i], result[prev] + time[i]);
					
					// 해당 건물의 요구 건물 갯수 1 감소
					--link[i];
					
					// 요구 건물이 없는 건물일 경우
					if (link[i] == 0)
					{
						queue.add(i);
					}
				}
			}
		}
		
		return result;
	}
}

분류

---

• 다이나믹 프로그래밍
• 그래프 이론
• 위상 정렬