백준 2252번 - 줄 세우기 (C++)

문제

해결 방법

위상 정렬을 사용하는 대표적인 문제이다. 정점기준 보내주는 간선들의 숫자, 받은 간선의 횟수를 저장하는 배열을 만들어서 이를 기반으로 큐를 사용하여 위상정렬을 했다.

아쉬웠던 점

초기에 큐에 넣는 과정을 입력구간에서 어떻게 잘 해결할 수 있을 것 같기도 한데, 결국 받은 간선을 저장한 배열을 순회하며 그 숫자가 0인 정점을 일일이 찾은게 뭔가 아쉽다.

코드

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    pair<int, int> Input_Pair;
    vector<int> In_Vec(N, 0); //A에 위치한 숫자. 간선 받은 횟수를 저장함.
    vector<vector<int>> Out_Vec(N); //B에 위치한 숫자들 저장. 간선 보내는 애들기준 어디로 보냈는지 저장함.
    for (int i = 0; i < M; ++i)
    {
        cin >> Input_Pair.first >> Input_Pair.second;
        In_Vec[Input_Pair.first - 1]++;
        Out_Vec[Input_Pair.second-1].emplace_back(Input_Pair.first - 1);
    }
 
    queue<int> Topological_Que;
    vector<int> Sort_Vec(N, 0);
    for (int i = 0 ; i < N; ++i) //초기부터 들어오는 간선이 0개인애들 큐에 넣어줌.
        if (In_Vec[i] == 0)
            Topological_Que.emplace(i);
 
    int Count = 0;
    while (!Topological_Que.empty())
    {
        for (auto i : Out_Vec[Topological_Que.front()]) //큐의 맨 앞 숫자에서 보내주는 간선들을 모두 삭제함 = 간선을 받는곳의 간선 갯수 -1 해줌.
        {
            In_Vec[i]--;
            if (In_Vec[i] == 0) //이때 받는곳의 간선이 0이 되었다면, 큐에 추가해줌.
                Topological_Que.push(i);
        }
        Sort_Vec[Count] = Topological_Que.front(); //정렬된 곳에 저장. (오름차순)
        Topological_Que.pop();
        Count++;
    }
 
    //오름차순으로 저장했기 때문에 역순으로 출력. 편의성을 위해 숫자를 1~N까지에서 0~N-1까지로 위에서 조정해주었기 때문에 출력값에 +1해줌.
    for (int i = N-1; i >= 0; --i) 
        cout << Sort_Vec[i]+1 << " ";
}

잡설 : 이왜골2?