2252 ์ค„์„ธ์šฐ๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜(์œ„์ƒ์ •๋ ฌ)

1. ๊ทธ๋ƒฅ ์œ„์ƒ์ •๋ ฌํ•˜๋ฉด๋œ๋‹ค.

๊ตฌํ˜„

1. Student ๊ตฌ์กฐ์ฒด : beforeCount : ์ด์ „์— ๋ช‡๊ฐœ์žˆ๋Š”์ง€ ์…ˆ, next : ํฐ ํ•™์ƒ๋“ค ๋‚˜์—ด, isChecked : ๋ผ์ธ์— ๋„ฃ์–ด์กŒ๋Š”์ง€ ํ™•์ธ
2. ์ฒ˜์Œ์— beforeCount๊ฐ€ 0์ธ ํ•™์ƒ๋“ค์„ ํ์— ๋„ฃ๊ณ , isCheked์— ์ฒดํฌํ•จ
3. ํ•˜๋‚˜์”ฉ ํ์—์„œ ๋นผ๋ฉด์„œ ์•„๋ž˜ ์‹œํ–‰
	-๋ผ์ธ์— ๋„ฃ๊ณ 
	-next์— ์žˆ๋Š” ํ•™์ƒ๋“ค์˜ beforeCount๋ฅผ 1๊ฐœ์”ฉ ์ค„์ž„
	-์ด๋•Œ, ๊ทธ ํ•™์ƒ์˜ beforeCount๊ฐ€ 0์ด ๋˜๋ฉด, ์ž„์‹œ ํ์— ๋„ฃ๊ณ  isChecked์— TRUE ํ‘œ์‹œ
4. ํ์—์„œ ๋‹ค ๋นผ๋ฉด, ์ž„์‹œ ํ๋ฅผ ํ์— ๋ณต์‚ฌ
5. ๋‹ค ๋น ์งˆ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณต
6. ์•ˆ๋„ฃ์–ด์ง„ ํ•™์ƒ๋“ค์„ ๋”ฐ๋กœ ๋’ค์— ์ง‘์–ด๋„ฃ์Œ

๊ธฐํƒ€

1. next์— ์žˆ๋Š” ํ•™์ƒ๋“ค์˜ beforeCount๋ฅผ ํ•˜๋‚˜์”ฉ ์ค„์ด๊ณ , 0๋˜๋ฉด ๋ฐ”๋กœ ์ง‘์–ด๋„ฃ๋Š” ๊ฒŒ, ๋‹ค์‹œ ์ฒ˜์Œ๋ถ€ํ„ฐ ๊ฒ€์‚ฌํ•˜๊ณ  ๋„ฃ๋Š” ๊ฒƒ๋ณด๋‹ค ํ›จ์”ฌ ๋น ๋ฅด๋‹ค.
2. for(int i = 0; i<q.size(); i++) {
	int cur = q.front();
	q.pop_front();
 ๋Š” ๋งค์šฐ ์œ„ํ—˜ํ•˜๋‹ค. pop_front() ๋  ๋•Œ๋งˆ๋‹ค size๊ฐ€ ๋‹ฌ๋ผ์ง€๋ฏ€๋กœ size๋Š” ์ฒ˜์Œ์— ๋‹ค๋ฅธ ๊ณณ์— length๋กœ ์ €์žฅํ•ด๋†“๊ณ  ํ•˜๋Š”๊ฒŒ ์ข‹๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <list>
#define MAX_STUDENT 32000
using namespace std;
 
typedef struct Student {
	int beforeCount;
	bool isChecked;
	vector<int> next;
} Student;
 
Student student[MAX_STUDENT];
int numOfStudent;
int line[MAX_STUDENT];
 
void setLine();
 
int main() {
	int numOfCompare;
	cin >> numOfStudent >> numOfCompare;
	for (int i = 0; i < numOfCompare; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		student[a].next.push_back(b);
		student[b].beforeCount++;
	}
 
	setLine();
	for (int i = 0; i < numOfStudent; i++)
		cout << line[i] + 1 << " ";
}
 
void setLine() {
	list<int> q;
	for (int i = 0; i < numOfStudent; i++)
		if (student[i].beforeCount == 0) {
			q.push_back(i);
			student[i].isChecked = true;
		}
 
	int lineIndex = 0;
	while (!q.empty()) {
		list<int> temp;
		int length = q.size();
		//๊บผ๋‚ด๋ฉด์„œ ์ค„ ์„ธ์šฐ๊ณ , next๋กœ ์—ฐ๊ฒฐ๋  ๊ณณ before ํ•˜๋‚˜์”ฉ ์ง€์šฐ์ž.
		for (int i = 0; i < length; i++) {
			int cur = q.front();
			q.pop_front();
			line[lineIndex++] = cur;
			for (int j = 0; j < student[cur].next.size(); j++) {
				student[student[cur].next[j]].beforeCount--;
				if (student[student[cur].next[j]].beforeCount == 0 && !student[student[cur].next[j]].isChecked) {
					temp.push_back(student[cur].next[j]);
					student[student[cur].next[j]].isChecked = true;
				}
			}
		}
		q = temp;
	}
 
	//check ์•ˆ๋œ๊ฑฐ ๊ทธ๋ƒฅ ํ•˜๋‚˜์”ฉ ์ง‘์–ด๋„ฃ๊ธฐ
	for (int i = 0; i < numOfStudent; i++)
		if (!student[i].isChecked)
			line[lineIndex++] = i;
}