[C++] ACM Craft(위상 정렬) - 1005

위상 정렬 알고리즘

---

1005번: ACM Craft

위 문제는 "위상 정렬 알고리즘"과 "다익스트라 알고리즘의 최단거리를 찾는 매커니즘"만 알면

아주 간단하게 풀 수 있는 문제입니다.

 

1. 위상 정렬 알고리즘으로 순환이 없는 방향 그래프의 노드들을 나열함

 

2. 나열하는 과정에서 조건에 해당하면 작업시간을 바꿔줌

조건 : 현재 노드까지의 작업 시간 + 다음 노드의 작업시간 > 지금까지 알려진 다음 노드까지의 작업시간

 

3. 그럼 각 노드까지의 최소 작업시간이 정해짐

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void ACM_Craft()
{
	int V, E;
	cin >> V >> E;

	// vector말고 일반 배열을 사용해도 무방
	vector<int> time(V);
	vector<int> result(V);
	vector<int> inDegree(V);
	vector<vector<int>> v(V);

	// 작업시간 세팅
	for (int i = 0; i < V; i++)
		cin >> time[i];

	for (int i = 0; i < E; i++)
	{
		int s, d;
		cin >> s >> d;

		// 방향그래프 세팅
		v[--s].push_back(--d);

		// 진입 차수 세팅
		inDegree[d]++;
	}

	queue<int> q;
	for (int i = 0; i < V; i++)
	{
		// 진입차수가 0인 노드 큐에 삽입
		if (inDegree[i] == 0) q.push(i);

		// 최소 작업시간 초기화
		result[i] = time[i];
	}

	while (!q.empty())
	{
		// 진입차수가 0인 노드 가져오기
		int currNode = q.front();
		q.pop();

		for (int i = 0; i < v[currNode].size(); i++)
		{
			int nextNode = v[currNode][i];
			// 다익스트라 최단 거리 구하는 공식처럼..
			result[nextNode] = max(result[nextNode], result[currNode] + time[nextNode]);

			if (--inDegree[nextNode] == 0)
				q.push(nextNode);
		}
	}

	int D;
	cin >> D;
	cout << result[--D] << "\n";


}


int main()
{
	int N;
	cin >> N;
	while (N--)
		ACM_Craft();

	return 0;
}