[BOJ] 3665번 : 최종 순위 C++ 풀이

팀의 초기 순위가 주어진다. 여기서 M개의 팀 쌍의 순위가 바뀌었다는 정보가 주어졌을 때, 가능한 경우인지 가능하다면 최종 순위는 몇 위인지 찾아야 한다. 그리고 가능하더라도 순위의 경우의 수가 1이 아니면?를 출력해야 한다.

순서가 정해져 있고, 이 순서를 기반으로 탐색을 진행해야 하기에 위상정렬을 떠올려볼 수 있다. 각 인덱스를 기준으로 자신보다 높은 순위가 몇개 남았는지를 세주자. 

M개의 정보가 들어온다. 이때 x, y중 초기 순위가 더 높은 값이 있고 작은 값이 있다. 이 둘을 바꾼다는 것은 이 우위가 바뀐다는 것이고, 간선의 방향을 뒤집어 줘야 한다. 그리고 나보다 높은 순위가 몇 개 남았는지 세는 값도 업데이트를 해줘야 한다.

자 이제 새롭게 만든 그래프를 기반으로 위상정렬을 돌리자. 이때 최종 순위의 size가 N이 아니라면 잘못된 정보로 인해 순위가 뒤죽박죽이 되어버린 경우다. 그러니 impossible를 출력하자.

그리고 위상정렬을 돌리는 과정에서 사용할 queue의 크기가 1보다 커질 수 없다. 만약 1보다 커진다면 중복된 순위가 존재하는 것이기에 확실한 순위를 정할 수 없다는 의미로 해석할 수 있고, 이때는 ?를 출력하자.

만약 이 두 조건을 만족한다면 새로운 순위가 정해진 것이다. 이때는 새로운 순위를 출력하면 된다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int T, N, arr[510], in[510], M;
vector<int> v, answer;
set<int> adj[510];
queue<int> q;
bool flag;

void init() {
    cin >> T;
    while (T--) {
        memset(arr, 0, sizeof(arr));
        memset(in, 0, sizeof(in));
        v.clear();
        flag = false;
        answer.clear();
        for (int i=0; i<510; i++) adj[i].clear();

        cin >> N;
        for (int i=0; i<N; i++) {
            int x;
            cin >> x;
            v.push_back(x);
            arr[x] = i;
        }
        for (int i=0; i<N; i++) {
            for (int j=0; j<i; j++) {
                adj[v[i]].insert(v[j]);
                in[v[j]]++;
            }
        }
        cin >> M;
        for (int i=0; i<M; i++) {
            int x, y;
            cin >> x >> y;
            if (arr[x] > arr[y]) swap(x, y);
            in[x]--, in[y]++;
            adj[y].erase(x);
            adj[x].insert(y);
        }

        for (int i=1; i<=N; i++) if (in[i] == 0) q.push(i);
        while (!q.empty()) {
            if (q.size() != 1) flag = true;
            auto curr = q.front();
            q.pop();
            answer.push_back(curr);
            for (int next : adj[curr]) {
                in[next]--;
                if (!in[next]) {
                    q.push(next);
                }
            }
        }
        if (answer.size() != N) cout << "IMPOSSIBLE" << '\n';
        else if (flag) cout << "?" << '\n';
        else {
            reverse(answer.begin(), answer.end());
            for (auto a : answer) {
                cout << a << " ";
            }
            cout << '\n';
        }

    }
} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}