[백준 C++] 1005번: ACM Craft

1. 문제

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

1005번: ACM Craft

 

2. 알고리즘 분류

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

 

3. 소스 코드

Key Point)
1. 순서가 정해져 있는 일련의 작업을 차례대로 수행할 때는 '위상 정렬' 알고리즘을 활용한다.
2. '위상 정렬' 알고리즘을 통해 탐색하면서 최대로 걸리는 시간을 갱신해 나간다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int costs[1003], inDegree[1003], total_cost[1003];
vector<int> graph[1003];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T, N, K, X, Y, W;

	// TestCase 수 입력
	cin >> T;

	// TestCase 수 만큼 반복
	for (int tc = 0; tc < T; tc++)
	{
		queue<int> q;

		// 초기화
		for (int i = 0; i < 1003; i++)
		{
			inDegree[i] = 0;
			graph[i].clear();
		}

		// 건물의 개수(N)과 규칙의 총 개수(K) 입력
		cin >> N >> K;

		// 건물 건설 시간 입력
		for (int i = 1; i <= N; i++)
			cin >> costs[i];

		// 건설 순서 입력
		for (int i = 0; i < K; i++)
		{
			cin >> X >> Y;

			graph[X].push_back(Y);
			inDegree[Y]++;
		}
		
		// 건설해야 하는 건물의 번호(W) 입력
		cin >> W;

		// 진입차수가 0인 건물 번호를 Queue에 저장
		for (int i = 1; i <= N; i++)
		{
			if (inDegree[i] == 0) q.push(i);
			total_cost[i] = costs[i];
		}

		// Queue가 빌 때까지 반복
		while (!q.empty()) 
		{
			int cur = q.front();
			q.pop();

			// 현재 건물에서 다음으로 넘어갈 수 있는 건물 탐색
			for (int i = 0; i < graph[cur].size(); i++)
			{
				int next = graph[cur][i];

				inDegree[next]--;	// 진입 차수 1씩 감소
				total_cost[next] = max(total_cost[next], total_cost[cur] + costs[next]);	// 다음 건물로 넘어갈 때 걸리는 최대 시간 계산

				// 진입 차수가 0이 되면, Queue에 저장
				if (inDegree[next] == 0)
					q.push(next);
			}
		}

		// 최종 걸리는 시간 출력
		cout << total_cost[W] << '\n';
	}


	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) 위상 정렬

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘

		// 진입차수가 0인 건물 번호를 Queue에 저장
		for (int i = 1; i <= N; i++)
		{
			if (inDegree[i] == 0) q.push(i);
			total_cost[i] = costs[i];
		}

		// Queue가 빌 때까지 반복
		while (!q.empty()) 
		{
			int cur = q.front();
			q.pop();

			// 현재 건물에서 다음으로 넘어갈 수 있는 건물 탐색
			for (int i = 0; i < graph[cur].size(); i++)
			{
				int next = graph[cur][i];

				inDegree[next]--;	// 진입 차수 1씩 감소
				total_cost[next] = max(total_cost[next], total_cost[cur] + costs[next]);	// 다음 건물로 넘어갈 때 걸리는 최대 시간 계산

				// 진입 차수가 0이 되면, Queue에 저장
				if (inDegree[next] == 0)
					q.push(next);
			}
		}