2252 줄세우기
알고리즘(위상정렬)
1
1. 그냥 위상정렬하면된다.
구현
1
2
3
4
5
6
7
8
9
1. Student 구조체 : beforeCount : 이전에 몇개있는지 셈, next : 큰 학생들 나열, isChecked : 라인에 넣어졌는지 확인
2. 처음에 beforeCount가 0인 학생들을 큐에 넣고, isCheked에 체크함
3. 하나씩 큐에서 빼면서 아래 시행
-라인에 넣고
-next에 있는 학생들의 beforeCount를 1개씩 줄임
-이때, 그 학생의 beforeCount가 0이 되면, 임시 큐에 넣고 isChecked에 TRUE 표시
4. 큐에서 다 빼면, 임시 큐를 큐에 복사
5. 다 빠질 때까지 반복
6. 안넣어진 학생들을 따로 뒤에 집어넣음
기타
1
2
3
4
5
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로 저장해놓고 하는게 좋다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}