최종 순위

• 문제

https://www.acmicpc.net/problem/3665

• 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N,M;

bool g[501][501];
bool visit[501];
int count[501];
vector<vector<int>> updated_rank;
queue<int> q;

void process_g(vector<int> &prev_rank){
    for(int i=0; i<prev_rank.size(); i++){
        int cur_idx = prev_rank[i];
        for(int j=i+1; j<prev_rank.size(); j++){
            int next_idx = prev_rank[j];
            g[cur_idx][next_idx] = true;
            count[next_idx]++;
        }
    }
}

bool isImpossible(){
    bool check[501];
    for(int i=0; i<=500; i++){
        check[i] = false;
    }

    queue<int> tmp_q;
    tmp_q.push(1);
    check[1] = true;
    bool isWrong = false;
    while(!tmp_q.empty()){
        int cur_idx = tmp_q.front();
        tmp_q.pop();
        for(int i=1; i<=N; i++){
            if(g[cur_idx][i]){
                if(check[i]){
                    isWrong = true;
                }else{
                    check[i] = true;
                    tmp_q.push(i);
                }
            }
        }
    }
    return isWrong;
}


void update_g(){
    for(auto rank : updated_rank){
        int sp = rank[0]; int ep = rank[1];
        if(g[sp][ep] == false){
            g[sp][ep] = true;
            count[ep]++;
            g[ep][sp] = false;
            count[sp]--;
        }else if(g[ep][sp] == false){
            g[ep][sp] = true;
            count[sp]++;
            g[sp][ep] = false;
            count[ep]--;
        }
    }
}

int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
    int T;
    cin >> T;
    while(T--){
        while(!q.empty()){
            q.pop();
        }
        for(int i=0; i<=500; i++){
            count[i] = 0;
            visit[i] = false;
        }
        for(int i=0; i<=500; i++){
            for(int j=0; j<=500; j++){
                g[i][j] = false;
            }
        }
        updated_rank.clear();


        cin >> N;
        vector<int> prev_rank;
        for(int i=0; i<N; i++){
            int input;
            cin >> input;
            prev_rank.push_back(input);
        }

        cin >> M;
        for(int i=0; i<M; i++){
            int sp, ep;
            cin >> sp >> ep;
            updated_rank.push_back(vector<int>{sp, ep});
        }

        process_g(prev_rank);
        update_g();

        bool isAmbigious = false;
        vector<int> cur_rank;

        while(true){
            for(int i=1; i<=N; i++){
                if(visit[i] == false && count[i] == 0){
                    q.push(i);
                    visit[i] = true;
                    cur_rank.push_back(i);
                }
            }
            if(q.size() == 0){
                break;
            }else if(q.size() > 1){
                isAmbigious = true;
                break;
            }

            while(!q.empty()){
                int cur_idx = q.front();
                q.pop();
                for(int i=1; i<=N; i++){
                    if(g[cur_idx][i])
                        count[i]--;
                }
            }
        }

        if(isAmbigious){
            cout << "?" << '\n';
        }else if(cur_rank.size() != N){
            cout << "IMPOSSIBLE\n";
        }else{
            for(int num : cur_rank){
                cout << num << ' ';
            }
            cout << '\n';
        }


    }
}

• 피드백
  • 위상정렬을 사용하는 문제이다.
  • 반성해야할 점은 impossible한 경우를 찾을 때, 사이클이 생길 때 그렇게 된 다는 것은 접근
  • 그러나 사이클을 큐를 사용해서 이제 방문할 노드가 이미 방문되었을 때의 경우를 사이클로 실수함
  • 사이클은 자신부터 시작해서 탐색하다 자기 자신을 찾을 때가 사이클이다.