[백준 2056번] 작업

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

2056번: 작업

풀이) 

위상정렬 알고리즘으로 해결할 수 있었다. 선행 작업들에 대한 차수를 inDegree 배열에 담아두고 0인 것부터 하나씩 꺼내서 계산해두고 꺼내진 정점과 연결되어 있는 작업들의 차수를 하나씩 내려주고 다시 0이 된 것들이 있다면 큐에 담아서 직전 과정을 반복하는 과정으로 해결할 수 있었다. 이번 문제와 같은 의존관계를 가지고 있는 그래프를 의존성 그래프라고 하는데, 이런 그래프에는 사이클이 존재하지 않고 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다.

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

int N, ans = 0;
int inDegree[10001], result[10001], cost[10001];
vector <int> v[10001];
queue <int> q;

void topologicalSort()
{
	for (int i = 1; i <= N; i++)
	{
		if (inDegree[i] == 0)
 		{
			q.push(i);
			result[i] = cost[i];
		}
	}

	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (int i = 0; i < v[now].size(); i++)
		{
			int next = v[now][i];
			result[next] = max(result[next], result[now] + cost[next]);
			if (--inDegree[next] == 0)
				q.push(next);
		}
	}
}

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

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int num;
		cin >> cost[i] >> num;
		while (num--)
		{
			int now;
			cin >> now;
			v[now].push_back(i);
			inDegree[i]++;
		}
	}
	topologicalSort();
	for (int i = 1; i <= N; i++)
		ans = max(ans, result[i]);
	cout << ans << "\n";

	return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!