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

1.문제 링크

작업

2. 풀이 전 계획과 생각

• 위상정렬 알고리즘

3. 풀이

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

vector<int> graph[10001];
int time[10001];
int indegree[10001];
int totalTime[10001];
int ans;

void topology_sort(int n){
    queue<int> q;

    for(int i=1;i<=n;i++){
        if(indegree[i]==0) {
        	q.push(i);
        	totalTime[i]=time[i];
        	ans = max(ans, totalTime[i]);
		}
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();
        ans = max(ans, totalTime[now]);

        for(int i=0;i<graph[now].size();i++){
            int next = graph[now][i];
			indegree[next]-=1;
            totalTime[next]=max(totalTime[next], totalTime[now]+time[next]);
            if(indegree[next]==0){
                q.push(next);
            }
        }
    }
}

int main(){
	int n;
	cin>>n;
	// 입력 
	for(int i=1;i<=n;i++){
		int t; 
		cin>>t;
		time[i]=t;
		int cnt;
		cin>>cnt;
		for(int j=0;j<cnt;j++){
			int temp;
			cin>>temp;
			graph[temp].push_back(i);
			indegree[i]+=1;
		}
	}
	
	topology_sort(n);
	
	// 답 출력 
	cout<<ans;
}

각 작업이 완성되는데 걸리는 시간을 모두 출력해야 하기 때문에 이것을 저장하기 위해 totalTime 배열을 선언한다.

처음에 진입차수가 0인 작업을 큐에 push하고 그 작업의 totalTime을 그 작업을 짓는 시간으로 초기화 한다.

그리고 큐에서 원소를 한개씩 빼주면서 그 다음으로 가는 인접노드(그래프로 표현함)에 대해서 totalTime을 초기화한다. 이때 다음 작업을 짓는 시간에 현재까지 시간을 더한 값이 더 크다면 그 값으로 갱신해주는 작업을 한다. 그리고 그 작업의 진입차수를 1 뺀다. 만약 그 작업의 진입차수가 0이되면 q에 삽입한다.

이 문제는 모든 작업을 짓는데 걸리는 최소시간을 구하는 문제이다. 따라서 q에서 원소를 pop할 때 ans와 totalTime[now]와 비교해서 더 큰 값으로 갱신해준다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감