[백준 BOJ] 2252. 줄 세우기
09 Sep 2021난이도
Gold II
문제 풀이
그냥 위상정렬의 결과를 출력하면 되는 문제이다. 주어지는 학생들의 번호를 하나의 노드라고 생각하면, 번호들의 순서가 곧 노드가 연결되는 순서이다. 그 순서를 알고 싶은 것이니, 위상정렬을 수행해 답을 구해내면 된다. 시간 복잡도는 위상정렬의 시간복잡도인 \(\scriptsize O(V + E)\)이다. (V는 노드 개수, E는 간선 개수) 하여튼 그냥 위상 정렬을 그대로 구현하면 된다. 위상정렬에 대한 자세한 설명
void topologySort(vector<vector<int>>& adj, vector<int>& count) {
vector<int> ret;
queue<int> q;
for(int i = 1; i <= N; ++i) {
if(count[i] == 0) q.push(i);
}
for(int i = 0; i < N; ++i) {
int now = q.front();
q.pop();
ret.push_back(now);
for(int j = 0; j < (int)adj[now].size(); ++j) {
if(--count[adj[now][j]] == 0) q.push(adj[now][j]);
}
}
for(auto& element : ret) cout << element << ' ';
}
요렇게 위상정렬을 써주고 출력하면, AC를 받을 수 있다.