BOJ2637/ C++

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

2056번: 작업

백준 온라인저지 2056번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

 

#include<iostream>
#include<vector>
#include<queue>
#define MAX 10001


using namespace std;

int N, M;
int sol;
int indegree[MAX];
int time[MAX];
vector<pair<int,int>> adj[MAX];

int max(int a, int b) {	return a > b ? a : b; }

void Input() {
	int a;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> time[i];
		cin >> M;
		while (M--) {
			cin >> a;
			indegree[i]++;
			adj[a].push_back({ i,time[i] });
		}
	}
}

void solution() {
	queue<int>q;
	for (int i = 1; i <= N; i++) {
		if (indegree[i]==0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		sol = max(sol, time[current]);
		for (auto itor : adj[current]) {
			int next = itor.first;
			int next_time = itor.second;
			time[next] = max(time[next], time[current] + next_time);
            //작업을 할때 선행작업이 2개 이상일때 그 중 가장 오래걸리는 작업이 끝나야
            //현제 작업을 할 수 있기때문에 가장 오래걸리는 작업의 시간을 찾아야함

			if (--indegree[next] == 0) {
				q.push(next);
			}
		}
	}
    cout << sol;
}

int main(void) {
	Input();
	solution();
}
/*
1번 반례
작업의 우선순의가 없을때
7
5 0
3 0
6 0
1 0
8 0
4 0
2 0
8

2번 반례
큐에 넣기전에 max 비교를 하게되면 이전 작업이 오래 걸리는 케이스에서 문제발생함
5
6 0
3 0
3 2 1 2
1 1 1
1 2 3 4

*/

아이디어

이전에 풀었던 백준 1516 문제와 비슷함 그런데 추가적으로 신경써야하는 것은 선행 작업이 없을 수도 있다는 것임

그래서 각 작업마다의 값을 비교하여 최댓값을 sol에 저장하여 마지막에는 sol을 출력하도록함