백준 2056 c++ "작업" -PlusUltraCode-

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

[필자 사고]

위상정렬 문제다. 

위상정렬 문제의 특징은 먼저 시행되어야 하는 노드들이 존재한다는 점이다. 

또한 순환하지 않는 그래프 여야 한다.

 

오랜만에 풀어서 햇갈렷는데 한번 코드를 풀고나니 다시 기억이 새록새록 했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

코드 흐름 해설

1. 입력 준비
   • N: 작업(노드)의 개수.
   • result: 각 작업이 끝나는 최소 시간을 저장하는 배열.
   • times: 각 작업을 단독으로 수행하는 데 걸리는 시간.
   • indegree: 각 작업의 진입 차수(선행 작업 개수).
   • arr: 그래프 인접 리스트. arr[u]는 작업 u 이후에 수행할 수 있는 작업들을 저장.
2. 입력 처리
   • 각 작업에 대해 t(걸리는 시간), cnt(선행 작업 수), 그리고 cnt개의 선행 작업 번호를 입력받음.
   • times[i] = t로 저장.
   • 선행 작업 pre가 있으면 arr[pre].push_back(i)로 그래프 연결.
   • 동시에 indegree[i]++ 해서 진입 차수 계산.
3. 큐 초기화
   • 진입 차수가 0인 작업들(즉, 시작할 수 있는 작업들)을 큐에 넣음.
   • result[i] = times[i]로, 선행 작업이 없는 경우 자신의 시간만큼 바로 완료됨.
4. 위상 정렬 실행
   • 큐에서 작업 cur를 꺼냄.
   • cur 다음에 할 수 있는 모든 작업 next에 대해:
     • result[next] = max(result[next], result[cur] + times[next])
       → 선행 작업들의 결과 중 가장 오래 걸리는 경로를 반영.
     • indegree[next]--. 모든 선행 작업이 처리되면 next를 큐에 넣음.
5. 출력
   • 모든 작업 중에서 가장 오래 걸린 작업 시간, 즉 max(result)를 출력.

---

핵심 아이디어

• 위상 정렬을 이용해 작업 순서를 보장하면서 각 노드까지의 최대 누적 시간을 계산한다.
• result[i]는 i번 작업이 끝나는 가장 빠른 시점이다.
• 마지막에는 모든 작업이 완료되는 데 걸리는 최소 총 시간이 max(result)로 구해진다.

[소스 코드]

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

int N;
vector<int> result;
vector<int> times;
vector<int> indegree;
vector<vector<int>> arr;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;

	result.assign(N + 1, 0);
	times.assign(N + 1, 0);
	indegree.assign(N + 1, 0);
	arr.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		int t, cnt;
		cin >> t >> cnt;
		times[i] = t;

		for (int k = 0; k < cnt; k++) {
			int pre;
			cin >> pre;
			arr[pre].push_back(i);
			indegree[i]++;
		}
	}

	queue<int> myQueue;

	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			myQueue.push(i);
			result[i] = times[i];
		}
	}
	
	while (!myQueue.empty()) {
		int cur = myQueue.front();
		myQueue.pop();

		for (int next : arr[cur]) {
			result[next] = max(result[next], result[cur] + times[next]);
			if (--indegree[next] == 0) {
				myQueue.push(next);
			}
		}
	}

	cout << *max_element(result.begin() + 1, result.end());
}