[백준 C++] 2252 줄 세우기 - 위상정렬

2252번: 줄 세우기

cpp

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

vector<list<int>> Neighbors;
vector<int> Entries;
vector<int> Sequence;
queue<int> SearchQueue;

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL);
‌cout.tie(NULL);

‌int N, M;
‌cin >> N >> M;

‌Neighbors.reserve(N);
‌for (int i = 0; i < N; ++i)
‌{
‌‌Neighbors.emplace_back(list<int>());
‌}

‌Entries.reserve(N);
‌for (int i = 0; i < N; ++i)
‌{
‌‌Entries.emplace_back(0);
‌}

‌for (int i = 0; i < M; ++i)
‌{
‌‌int A, B;
‌‌cin >> A >> B;

‌‌Neighbors[A - 1].emplace_back(B - 1);
‌‌++Entries[B - 1];
‌}

‌int i = 0;
‌for (int& Entry : Entries)
‌{
‌‌if (Entry == 0)
‌‌{
‌‌‌SearchQueue.push(i);
‌‌}

‌‌++i;
‌}

‌Sequence.reserve(N);
‌while (!SearchQueue.empty())
‌{
‌‌int Current = SearchQueue.front();
‌‌SearchQueue.pop();

‌‌Sequence.emplace_back(Current);
‌‌for (const int& Neighbor : Neighbors[Current])
‌‌{
‌‌‌--Entries[Neighbor];
‌‌‌if (Entries[Neighbor] == 0)
‌‌‌{
‌‌‌‌SearchQueue.push(Neighbor);
‌‌‌}
‌‌}
‌}

‌for(const int& Student : Sequence)
‌{
‌‌cout << Student + 1 << ' ';
‌}
}

---

해당 문제는 사이클이 없는 방향 그래프에서 노드 순서를 찾는 문제로

위상 정렬 알고리즘을 사용해서 다음과 같은 단계로 풀었습니다.

 

1. 인접 리스트를 통해서 진입차수 계산

2. 진입 차수가 0인 미방문 노드 선택 후 위상 정렬 배열에 추가

3. 해당 노드의 인접 노드들의 진입 차수 업데이트

4. 모든 노드가 위상 정렬 배열에 추가될 때까지 2~3번 반복