[기출 상] N개의 작업공정 - 위상정렬

[문제]

N개의 작업공정이 있다. 공정마다 소요시간이 있고, 선행관계가 있다면 반드시 선행 공정이 끝나야만 다음 공정으로 넘어갈 수 있다. 임의로 주어지는 공정에 대해 목표되는 공정까지 소요되는 최소시간을 구하는 프로그램을 작성하라.

첫째줄에 공정수(N), 관계수(R)를 입력한다.

그 다음줄에 공정에서 소요되는 시간 N개를 입력하고, 그 다음 줄부터 공정간의 관계를 R줄에 걸쳐 입력한다. 공정간의 관계는 "선행공정번호 후행공정번호"순으로 입력한다. 그 다음줄에 목표되는 공정 번호를 입력한다.

 

[풀이]

공정 간 선후행관계가 있고, 이를 반드시 지켜야하므로 위상정렬 알고리즘을 이용해 풀 수 있다. 먼저 진입차수가 0이면 선행공정이 없다는 의미이므로 time[i]에 n[i] 값을 넣는다.(time[i]는 i 번째 공정에 대해 소요되는 시간을 의미한다.) 이후 while문에서 큐에서 나온 공정과 인접한 공정에 대해 진입차수를 재계산해주고 진입차수가 0이되면 큐에 넣는다. 이때, time[i]는 큐에서 나온 v번째 공정만큼 걸린 시간인 time[v]와 현재 i번째 공정에 소요시간인 n[i]의 합과 i번째 공정까지 걸린 시간인 time[i] 중 큰 값을 넣어준다. 

예를 들어, B와 C가 큐에 들어가 있는 상황에서 B가 먼저 큐에서 나왔다면 인접한 D공정의 time[D]는 time[B](=30)+n[D](=20) = 50 이 될 것이다. 그 후 C 공정이 큐에서 나온 후에 time[C](=110)+n[D](=20) = 130이 time[D] = 50보다 크므로 time[D]에는 130이 새로 저장된다.

마지막으로 time[goal-1]을 반환해주면 된다.(goal은 공정의 번호를 의미, time 인덱스는 0부터 시작했으므로 -1을 해준다.)

(참고로, 공정의 번호는 1부터 시작했고, 모든 배열의 저장은 0부터 시작하게 맞춰주었음.) 

 

[코드]

#include <iostream>
#include <queue>
using namespace std;
#define MAX 101
#define max(x,y) (x>y)?x:y

int solution(int n[],int r[][100],int goal,int N,int R){
  //임의로 주어지는 공정에 대해 목표되는 공정까지 소요되는 최소시간을 구해라.
	//위상정렬. 
	queue<int> q;
	int adj[MAX][MAX];
	int time[MAX];
	vector<int> in(N+1, 0);
	//진입차수 계산
	for(int i=0; i<R; i++){
		in[r[i][1]-1]++; 
		adj[r[i][0]-1][r[i][1]-1] = 1;
	}
	
	//진입차수가 0이면 큐에 넣기
	for(int i=0; i<N; i++){
		if(in[i] == 0){
			q.push(i);
			time[i] = n[i]; //진입차수가 0 -> 선행공정이 없으므로 자기 공정 시간만큼 소요.
		}
			
	}
	
	while(!q.empty()){
		int v = q.front();
		q.pop();

		int max = -1;
		for(int i=0; i<N; i++){
			//인접 노드의 진입차수 재계산
			if(adj[v][i]==1){
				//인접한 노드들 중 더 큰 공정시간 선택
				time[i] = max(time[v]+n[i], time[i]);
				in[i]--;
				if(in[i] == 0) //진입차수 0이면 큐에 넣기
					q.push(i);
			}
		}
	}
	
	return time[goal-1];
}


int main() {
    int N; //공정수
    int R; //관계수
    int n[100] = {0};
    int r[100][100] = {0};
    int goal, k;

		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; // 목표 공정 번호
    k = solution(n, r, goal, N, R);
    cout << k; //최소 소요시간
}