최종 순위 3665

문제

접근 방법

위상 정렬을 통해 순서를 정해주면 된다. 1등의 경우 자신을 제외한 모든 사람인 N-1개의 진입 차수, 2등은 N-2개, N등은 0개로 한 뒤 N등부터 차례대로 큐에 집어넣어 다른 등수의 진입차수를 줄여주면 된다. 그렇게 되면 순위를 얻을 수 있게 된다.
상대적인 등수가 바뀐다면 진입 차수를 변경해준 뒤 방향을 바꾸면 된다.

코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
bool graph[501][501];
int inDegree[501], nums[501], n, m, a, b;
stack<int> ret;
void input()
{
    memset(graph, false, sizeof(graph));
    memset(inDegree, 0, sizeof(inDegree));
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> nums[i];
    for (int i = 1; i <= n; ++i)
    {
        for (int j = n; j > i; --j)
        {
            ++inDegree[nums[i]];
            graph[nums[j]][nums[i]] = true;
        }
    }
    cin >> m;
    while (m--)
    {
        cin >> a >> b;
        if (graph[b][a])
        {
            swap(a, b);
        }
        --inDegree[b];
        ++inDegree[a];
        graph[b][a] = true;
        graph[a][b] = false;
    }
}
void solve()
{
    ret = stack<int>();
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!inDegree[i])
            q.push(i);
    for (int i = 1; i <= n; ++i)
    {
        if (q.empty())
        {
            cout << "IMPOSSIBLE"
                 << "\n";
            return;
        }
        int cur = q.front();
        q.pop();
        ret.push(cur);
        for (int j = 1; j <= n; ++j)
        {
            if (graph[cur][j] && !(--inDegree[j]))
                q.push(j);
        }
    }
    while (!ret.empty())
    {
        cout << ret.top() << " ";
        ret.pop();
    }
    cout << "\n";
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--)
    {
        input();
        solve();
    }
}

풀이

순위를 어떻게 해야 할지 고민하다가 다른 사람 것을 참고했다.
?의 경우는 존재하지 않았다.

이 문제에서 필요로 하는 건 등수를 위상 정렬로 나타낼 수 있는지와 위상 정렬에서 사이클이 생기는 경우를 확인하는 법이다.

사이클이 생기는 것을 확인하기 위해선 n번만큼 반복문을 돌며 큐가 비어있는지 확인하면 된다. (사이클의 경우 진입차수 겹치므로 0이 되지 못한다)

등수가 바뀌는 경우는 뒤에 숫자가 무조건 높은 등수이지 않기에 방향을 확인하고 숫자의 순서를 변경해주는 등의 작업을 해줘야 한다.