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;
}