[코딩인터뷰 완전정복] 4.7 순서 정하기

Q : 프로젝트의 리스트와 프로젝트들 간의 종속 관계(즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두 번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻)가 주어졌을 때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다.

예시 입력 :  프로젝트: a, b, c, d, e, f 종속관계: (a,d),(f,b),(b,d),(f,a),(d,c) 출력 : f,e,a,b,d,c

 

#include <iostream>
#include <iterator>
#include <queue>
#include <list>

template <class T>
std::list<T> ordering(std::list<T> proj, std::list<std::pair<T,T>> relation) {
	int size = proj.size();
	int *depNum = new int[size];
	bool** rel = new bool*[size];
	std::queue<int> taskQueue;
	std::list<T> taskList;
	typename std::list<T>::iterator itr;
	for (int i = 0; i < size; i++) {
		rel[i] = new bool[size];
		depNum[i] = 0;
		for (int j = 0; j < size; j++) {
			rel[i][j] = false;
		}
	}

	for (std::pair<T, T> pair : relation) {
		int first = 0;
		int second = 0;

		itr = proj.begin();
		while (pair.first != *itr) {
			first++;
			itr++;
		}
		itr = proj.begin();
		while (pair.second != *itr) {
			second++;
			itr++;
		}
		
		rel[first][second] = true;
		depNum[second]++;
	}

	for (int i = 0; i < size; i++) {
		if (depNum[i] == 0) taskQueue.push(i);
	}
	while (taskQueue.size() != 0) {
		int next = taskQueue.front();
		taskQueue.pop();
		depNum[next] = -1;
		for (int i = 0; i < size; i++) {
			if (rel[next][i]) {
				depNum[i]--;
				if (depNum[i] == 0) taskQueue.push(i);
			}
		}
		itr = proj.begin();
		while (next != 0) {
			next--;
			itr++;
		}
		taskList.push_back(*itr);
	}
	for (int i = 0; i < size; i++) {
		printf("%d : %d\n", i, depNum[i]);
		try {
			if (depNum[i] != -1) throw std::invalid_argument("circulation");
		}
		catch (std::invalid_argument& e) {
			printf("circulation error");
			exit(0);
		}
	}
	return taskList;
}

int main() {
	std::list<char> project;
	std::list<std::pair<char, char> > relation;

	project.push_back('a');
	project.push_back('b');
	project.push_back('c');
	project.push_back('d');
	project.push_back('e');
	project.push_back('f');

	relation.push_back(std::pair<char,char>('a', 'd'));
	relation.push_back(std::pair<char, char>('f', 'b'));
	relation.push_back(std::pair<char, char>('f', 'a'));
	relation.push_back(std::pair<char, char>('b', 'd'));
	relation.push_back(std::pair<char, char>('d', 'c'));

	project = ordering(project, relation);

	for (char proj : project) {
		printf("%c", proj);
	}
}

 

1. 각 프로젝트가 선행 프로젝트의 갯수를 알고 있게 한다.
2. 각 프로젝트가 종속되어 있는 프로젝트들을 알고 있게 한다.

3. 선행 프로젝트가 없는 프로젝트들을 Queue에 담는다.

4. Queue에 담겨있는 프로젝트를 List에 넣고 처리상태로 바꾼다. 
5. 종속되어 있는 프로젝트들의 선행 프로젝트 갯수를 하나씩 줄여주고, 선행 프로젝트의 갯수가 0개가 되는 프로젝트는 Queue에 담는다.
6. Queue가 빌때까지 반복한다.

7. 처리되지 않은 프로젝트들은 종속 관계에 순환이 있는 프로젝트들과 그에 종속된 프로젝트들이다.
이 경우 Error를 발생시킨다.

8. 모든 프로젝트들이 처리상태이면, List를 반환한다.