[SWEA 3952] 줄 세우기 - C++

SW Expert Academy

문제

삼성 초등학교 학생들을 줄을 세우려고 한다.
하지만 아이들은 쓸데없는 자존심이 있다.
“내가 쟤보다는 뒤에 서야됩니다.” 와 같은 이야기를 하는 아이들이 있다.
아이들의 번호는 1부터 N까지로 하고, 저런 아이들의 데이터가 주어진다. 만약 a b 라는 데이터가 주어지면 b라는 친구는 항상 a뒤에 서야한다.
(바로 뒤가 아니어도 된다. 순서상 뒤에만 있으면 된다.)
이런 가능한 순서 중 아무거나 출력하시오.

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20)
각 테스트 케이스의 첫 줄에는 학생의 수 N과 순서의 개수를 나타내는 M이 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ M ≤ 150,000,)
그 다음 M개의 줄에는 순서를 나타내는 두 개의 정수 a, b가 빈칸을 두고 주어진다. (1 ≤ a,b ≤ N)

풀이

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, M;
vector<int> degree, result;
vector<vector<int>> graph;
queue<int> que;
 
void custom_sort()
{   
    int node;
    for (int i = 1; i <= N; i++)
    {
        if (degree[i] == 0)
        {
            que.push(i);
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (que.empty())
        {
            return;
        }
        node = que.front();
        que.pop();
        result[i] = node;
        for (int j = 0; j < graph[node].size(); j++)
        {
            int temp = graph[node][j];
            degree[temp] -= 1;
            if (degree[temp] == 0)
            {
                que.push(temp);
            }
        }
    }
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N >> M;
        degree.assign(N + 1, 0);
        result.assign(N + 1, 0);
        graph.assign(N + 1, vector<int>(0, 0));
        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            graph[a].emplace_back(b);
            degree[b] += 1;
        }
        custom_sort();
        cout << "#" << test_case;
        for (int i = 0; i < N; i++)
        {
            cout << " " << result[i];
        }
        cout << endl;
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

해결방법

위상정렬 유형의 문제입니다. 위상정렬을 구현해서 조건에 맞는 경우를 출력하면 되는 문제입니다.