[EPPER] 12회 10번

문제

 

---

풀이

 

어렵다. 큐를 이용하라는데 c++도 아닌 마당에 큐를 하나하나 구현하고 싶진 않아서 그냥 내맘대로 구현했다. 그리고 이게 더 편한 것 같다. 큐로 구현하려면 내가 쓴 논리 구조랑 아주 다른 방법으로 해야할 듯하다.

 

factory 구조체를 만들었다. 이 구조체에는 공정별 소요 시간과 선행되어야 하는 공정이 있는지 있다면 그 선행 공정의 개수와 그 종류를 저장하고 마지막으로 해당 공정이 완료된 공정인지 확인하는 bool 변수를 넣었다.

 

먼저 공정별 소요 시간을 저장하며 선행 공정의 수인 b_num을 0으로 초기화 하고 isDone도 false로 초기화한다. 그리고 나서 선행공정의 관계를 입력받아 저장한다. 이 부분 코드가 좀 복잡해보일 수 있지만 어려운 부분은 아니다. 마지막으로 목표 공정 번호를 저장한다.

 

입력을 다 받았으니 while loop를 돌린다. 반복문을 빠져나올 조건은 '목표 공정이 완료될 것'이다. 일단 모든 공정에 대해 이번에 해당 공정을 할 수 있는지 isPos 함수로 확인한다. 특정 공정을 이번에 할 수 있는 조건은 다음과 같다.

 

1. 아직 한 일이 아닐 것

2. 선행 공정이 없을 것

3. 선행 공정이 있다면, 그 모든 선행 공정을 이미 한 상태일 것

 

해당 조건에 맞춰서 함수를 작성한다. isPos 함수를 통해 이번에 할 수 있는 공정이라는 것을 확인하면 각각의 공정 index와 소요 시간을 check_arr와 temp_arr에 저장한다. 왜 바로바로 반영하지 않고 굳이 저장해뒀다가 한번에 반영하는 이유가 궁금할 수 있다. 그 이유를 위 입력 예시로 설명하도록 하겠다.

공정 A는 지금 당장 할 수 있는 일이다. 그래서 공정 A의 isDone을 바로 true로 바꿨다. 순서대로 모든 배열을 탐색할테니 그 뒤로 B, C, D를 탐색할 것이다. 그리고 A의 isDone이 true이니 공정 B, C도 지금 당장 할 수 있는 일로 체크될 것이고 연쇄적으로 공정 D도 당장 할 수 있는 일로 체크될 것이다. 이런 문제를 막고자 배열을 탐색 한 뒤에 한번에 결과를 반영하는 것이다.

아무튼 이렇게 배열을 돌고나면 check_arr과 temp_arr에는 지금 당장 동시에 진행할 수 있는 공정이 쌓일 것이다. 이 중에서 가장 오래 걸리는 일만 끝나면 바로 다음 일을 할 수 있으니 가장 긴 공정만 sum에 더해주고, 이제서야 해당 공정들을 다 true로 체크한다.

 

check_arr, temp_arr의 회차별 원소들을 정리했다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct factory{ //소요시간, 선행공정, 작업했는지 확인
	int dur;
	int b_num;
	int before[101];
	bool isDone;
}factory;
factory task[101];

bool isPos(factory t) {
	bool allDone = true;
	if (t.isDone) //이미 한 일이면 또 할 이유가 없음
		return false;
	if (t.b_num == 0) //선행되어야 하는 일이 없으면 바로 할 수 있음
		return true;
	for (int i = 0; i < t.b_num; i++) { //선행되어야 하는 모든 일들을 이미 했다면 바로 할 수 있음
		if (task[t.before[i]].isDone == false)
			allDone = false;
	}
	if (allDone)
		return true;
	else
		return false;
}

int main() {
	int N, R;
	int temp_b, temp_a;
	int temp_arr[101];
	int check_arr[101];
	int sum = 0;
	int obj_t;

	scanf("%d %d", &N, &R);
	for (int i = 1; i <= N; i++) { //구조체에 값 채움
		scanf("%d", &task[i].dur);
		task[i].b_num = 0;
		task[i].isDone = false;
	}
	for (int i = 0; i < R; i++) {
		scanf("%d %d", &temp_b, &temp_a);
		task[temp_a].before[task[temp_a].b_num++] = temp_b; //선행되어야 하는 공정을 입력
	}
	scanf("%d", &obj_t); //마지막 공정
	while (true) {
		int arr_cnt = 0;
		if (task[obj_t].isDone==true) //마지막 공정까지 했으면 반복문 빠져나옴
			break;
		for (int i = 1; i <= N; i++) { //모든 공정에 대해 이번에 할 수 있는 일인지 확인
			if (isPos(task[i])) {
				check_arr[arr_cnt] = i; //나중에 isDone을 한번에 true로 바꾸기 위해 배열에 넣어둠
				temp_arr[arr_cnt++] = task[i].dur; //걸리는 시간을 저장하는 배열
			}
		}
		int max_task = temp_arr[0];
		for (int i = 1; i < arr_cnt; i++) { //가장 오래 걸리는 일을 체크
			if (max_task < temp_arr[i])
				max_task = temp_arr[i];
		}
		sum += max_task; //sum에 가장 오래 걸리는 일만 더해줌
		for (int i = 0; i < arr_cnt; i++) //일을 다 했으므로 isDone을 true로 바꿔줌
			task[check_arr[i]].isDone = true;
	}
	printf("%d", sum);
}