줄 세우기 2252

문제

접근 방법

위상 정렬을 알아보기 위해 풀어봤다.
위상 정렬이란 순서가 정해진 작업을 순서대로 하기 위한 것이다.
순서를 알아내기 위해서는 진입차수를 기록하면 되는데 기록된 진입차수가 0인 것부터 차례대로 빼내면 순서대로 빠지는 것을 알 수 있다.
그러한 점을 활용하여 뒤에 서야 하는 학생에 진입차수를 올려주고 앞에서야 하는 학생은 뒤에 서야 하는 학생을 기록해주면 위상정렬을 해줄 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, a, b;
    cin >> N >> M;
    queue<int> q;
    vector<int> inDegree(N + 1);
    vector<vector<int>> graph(N + 1, vector<int>());
    while (M--)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        ++inDegree[b];
    }
    for (int i = 1; i <= N; ++i)
        if (!inDegree[i])
            q.push(i);
    while (!q.empty())
    {
        int cur = q.front();
        cout << cur << " ";
        q.pop();
        for (int next : graph[cur])
        {
            if (--inDegree[next] == 0)
                q.push(next);
        }
    }
}

풀이

DFS 또는 BFS를 활용하여서 풀어주면 된다. (DFS는 스택을 통해 방문을 확인하고 BFS는 큐를 통해 진입차수를 확인한다)
BFS를 활용하여 진입차수가 0인 것을 빼다 보면 0이 아닌 것들도 0되기에 결과적으론 순서대로 모든 정점을 방문할 수 있다.
자주 보이지는 않았지만 그래도 알아두면 좋은 유형인 것 같다.