[C/C++] 백준 2056번 - 작업

✏️ 문제 링크

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

2056번: 작업

✏️ 문제 설명

 

✏️ 문제 풀이

위상 정렬로 접근해서 푸는 문제 

일반적인 위상정렬로 구현하고 큐를 탐색하는 과정에서 살짝만 추가하면 문제를 해결할 수 있습니다

작업 시간 배열, 선행 관계 배열, 그리고 정답 출력 배열을 만든 후 큐를 돌리면서

ans[next] = max(ans[next], ans[node] + workTime[node])로 갱신해주시면 됩니다.

정답은 max(ans)

 

✏️ 문제 코드

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

vector<int>workTime;
vector<vector<int>>mlist;
vector<int>indegree;
vector<int>ans;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, count, f;
	cin >> N;
	workTime.resize(N + 1);
	mlist.resize(N + 1);
	indegree.resize(N + 1);
	ans.resize(N + 1);

	int c = 0;
	for (int i = 1; i <= N; i++) {
		cin >> workTime[i];
		cin >> count;
		if (count == 0)
			c++;
		for (int j = 0; j < count; j++) {
			cin >> f;
			mlist[f].push_back(i);
			indegree[i]++;
		}
	}

	queue<int>q;
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			ans[i] = workTime[i];
		}
	}

	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int next : mlist[node]) {
			indegree[next]--;
			ans[next] = max(ans[next], ans[node] + workTime[next]);
			if (indegree[next] == 0)
				q.push(next);
		}
	}

	int max = INT_MIN;
	for (int i = 1; i <= N; i++) {
		if (max < ans[i])
			max = ans[i];
	}
	cout << max;
}

 

 

✏️ 비슷한 문제

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

1516번: 게임 개발

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

1005번: ACM Craft