[EPPER/13회 9번]N개의 작업공정(상-4)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 101
using namespace std;

/*
공정끼리 선후관계가 존재하고, 선후관계에 따라 공정을 처리해한다.

선후관계가 있는 것은 보통 방향그래프로 나타낼 수 있고, 이는 위상정렬로 처리가능하다.

위상정렬 알고리즘?
선수과목 등 선행 관계가 있는 자료구조를 정렬하는 알고리즘
사이클이 없는 방향그래프에서 선행순서를 위배하지 않으면서 정점을 순서대로 정렬함
방향그래프에서 <u,v>가 있다면 u가 v에 대해 선행됨

위상정렬 방법
1. 진입차수가 0인 정점을 큐에 삽입함
2. 큐에서 원소를 꺼내 에지를 제거한 후 진입 차수를 재계산
3. 모든 정점이 제거될때 까지 1~2를 반복함
4. 모든 원소를 방문하기 전 진입 차수가 0인 것이 없으면, 사이클이 존재해서 해가 없음 



*/


int adj[MAX][MAX] = {0,};
int indegree[MAX] = {0,};
int timeA[MAX] = {0,};

int solution(int n[], int r[][100], int goal, int N, int R){
    queue<int> q;
		
	
	//선행관계를 파악하기 위한 배열을 초기화 
	//u->v 인 경우 adj[u][v] = 1을 대입해둠 
		for(int i=0; i<R; i++){
			
			//입력받은 연관관계 [0] 선행 [1] 후행 
			int u = r[i][0];
			int v = r[i][1];
			adj[u][v] = 1;
			
			//선행해야하는 기기가 몇개나 있는지에 대한 배열 업데이트 
			indegree[v]++;
		}
	
	//선행해야하는 공정이 없는 경우 q에 넣고 시간을 업데이트 
		for(int i=1; i<=N; i++){
			if(indegree[i]==0){ //공정이 없는 경우 
				timeA[i]= n[i-1]; //해당하는 시간을 대입( 실제로 index가 1씩 차이나서 -1있음 )
				q.push(i); //큐에 넣음 
			}
		}
	
		while(!q.empty()){ //큐가 빈 큐가될 떄 까지 진행 
			int p=q.front(); // 맨 앞에있는 것을 빼내기 
			q.pop();
			
			for(int i=1; i<=N; i++){
				if(adj[p][i] == 1){ //빼낸것을 선행으로 가지는 공정이 있으면 
					timeA[i] = max(timeA[i], timeA[p] + n[i-1]); //현재 , 현재 + 지금 공정진행 중 최대값으로 변경 
					indegree[i]--; // 하나 줄여줌 
					if(indegree[i] == 0) q.push(i); //공정이 한개 빠져서 0이된 공정이 있다면 큐에 다시넣음 
				}
			}
		}
		
		
		return timeA[goal];
}


int main(){
		
		int N;
		int R;
		int  n[100]={0} ;
		int r[100][100]={0};
		int goal;
		
		cin>>N>>R;

		for(int i=0;i<N;i++) {
			cin>>n[i];
		}
		for(int k=0;k<R;k++) {
			for(int j=0;j<2;j++) {
				cin>>r[k][j];
			}
		}
		
		cin>>goal;
		cout<<solution(n,r,goal,N,R);
		
}

 

 

벡터로 바꿈

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define MAX 101
using namespace std;

/*
공정끼리 선후관계가 존재하고, 선후관계에 따라 공정을 처리해한다.

선후관계가 있는 것은 보통 방향그래프로 나타낼 수 있고, 이는 위상정렬로 처리가능하다.

위상정렬 알고리즘?
선수과목 등 선행 관계가 있는 자료구조를 정렬하는 알고리즘
사이클이 없는 방향그래프에서 선행순서를 위배하지 않으면서 정점을 순서대로 정렬함
방향그래프에서 <u,v>가 있다면 u가 v에 대해 선행됨

위상정렬 방법
1. 진입차수가 0인 정점을 큐에 삽입함
2. 큐에서 원소를 꺼내 에지를 제거한 후 진입 차수를 재계산
3. 모든 정점이 제거될때 까지 1~2를 반복함
4. 모든 원소를 방문하기 전 진입 차수가 0인 것이 없으면, 사이클이 존재해서 해가 없음 



*/


int adj[MAX][MAX] = {0,}; //선행관계를 저장한 2차배열 adj[u][v] == 1이면, u->v (u가 v에 대해 선행 )
int indegree[MAX] = {0,}; //배열index에 해당하는 공정이 몇개나 선행 공정을 가졌는지 저장하는 배열 
int timeA[MAX] = {0,}; // 공정이 index인 애의 최소 소요시간 


int solution(vector<int> n, vector<vector<int>>r, int goal, int N, int R)
{
    queue<int> q;
		
	 //adj배열을 초기화 
		for(int i=0; i<R; i++){
			int u = r[i][0]; //r배열에 처음이 선행
			int v = r[i][1]; //r배열 다음이 후행 
			adj[u][v] = 1; //u->v관계에 1 넣어놓기 
			indegree[v]++;//후행index에서 ++ 
		}
	
	
	//공정을 돌리면서 선행 공정이 없으면 q에 집어넣음 
		for(int i=1; i<=N; i++){
			if(indegree[i]==0){ // 선행공정이 없음 
				timeA[i]= n[i-1]; // 시간을 저장하는데 n : i-1이어야함 (idex때문에)
				q.push(i); //큐에 넣기 
			}
		}
	
	
	//이제 큐를 이용 
		while(!q.empty()){
			//빼오고 뺀거 삭제 
			int p=q.front();
			q.pop();
			
			//모든 공정확인 
			for(int i=1; i<=N; i++){
				if(adj[p][i] == 1){ // 뺸거를 선행하는 무언가가 있다면 
					timeA[i] = max(timeA[i], timeA[p] + n[i-1]); //시간을 갱신시켜줌 
					indegree[i]--;//그리고 그친구는 1을 잃음 
					if(indegree[i] == 0) q.push(i); //뺴서 0이되었다면 q에 넣어줌 
				}
			}
		}
		
		
		return timeA[goal];
}


int main(){
		
		int N;
		int R;
		vector<int>n;
		//int  n[100]={0} ;
		vector<vector<int>> r; 
		//int r[100][100]={0};
		int goal;
		
		cin>>N>>R;

		int nn,rr;
	
		for(int i=0;i<N;i++) {
			cin>>nn;
			n.push_back(nn);
		}
	
	
		vector<int>line;
	
		for(int k=0;k<R;k++) {
			for(int j=0;j<2;j++) {
				cin>>rr;
				line.push_back(rr);
			}
			r.push_back(line);
			line.clear();
		}
		
		cin>>goal;
		cout<<solution(n,r,goal,N,R);
		
}