[G4] 백준 2056번 작업 C++ 위상 정렬

리뷰

 

max이 하나가 정답을 좌지우지 했다 ㅠㅜ

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

 

전역 변수

• n : 작업의 개수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 작업 시간 정보 times와 인접 리스트를 초기화할 정수 벡터 path를 n + 1크기로 초기화 한다.
2. 1부터 n개의 각각의 작업에 걸리는 시간을 times 벡터에 저장해 준다.
3. 이후 선행이 필요한 작업을 인접 리스트로 추가해 준다, 역방향으로 삽입해 주어야 한다.
4. 선행 작업의 개수를 저장할 벡터 cnt를 n + 1크기, 기본값은 0인 상태로 초기화 해준다.
5. 각 작업을 순회하며 작업의 인접리스트에 저장된 작업을의 cnt를 증가시켜준다.
6. 정수형 큐 q를 초기화 한 후에 cnt가 0인 작업을 큐에 넣어준다.
7. 정답을 저장할 정수형 벡터 ans를 n + 1크기, 기본값은 0인 상태로 초기화 해준다.
8. 큐가 빌때까지 while루프를 돌며 큐에서 값을 하나씩 빼준다.
9. 작업에 걸리는 시간을 ans의 현재 작업 인덱스의 값에 추가해 준다.
10. 현재 작업의 인접리스트를 순회하며 해당 인접리스트의 ans값을 현재 작업과 해당 작업의 큰값으로 갱신해 준다.
11. 해당 작업의 cnt를 감소시켜준다. 만약 cnt가 0이 되었다면 해당 작업을 큐에 추가해 준다.
12. while루프가 종료된 후 max_val을 0으로 초기화 한 후 ans벡터에서 가장 큰 값을 저장해 준다.
13. max_val을 출력해 준다.

 

참고 사항

우선 순위가 존재하는 작업의 ans값을 갱신할땐 꼭 현재 작업 시간과 새로운 작업 시간 중 큰 값으로 초기화 해주어야 한다.

 

관련 테스트 케이스

3
5 0
2 0
3 2 1 2

// ans = 8

 

 

정답 코드

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

using namespace std;

int n;

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

	cin >> n;
	vector<vector<int>> path(n + 1);
	vector<int> times(n + 1);
	for (int i = 1; i <= n; i++) {
		int t, c; cin >> t >> c;
		times[i] = t;
		while (c--) {
			int f; cin >> f;
			path[f].push_back(i);
		}
	}

	vector<int> cnt(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j : path[i]) cnt[j]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) if (!cnt[i]) q.push(i);
	
	vector<int> ans(n + 1, 0);
	while (!q.empty()) {
		int cn = q.front(); q.pop();
		ans[cn] += times[cn];
		for (int i : path[cn]) {
			ans[i] = max(ans[i], ans[cn]);
			if (!--cnt[i]) q.push(i);
		}
	}

	int max_val = 0;
	for (int i = 1; i <= n; i++) max_val = max(max_val, ans[i]);
	cout << max_val;
}