[백준] 최종 순위

최종순위 링크

문제

총 n개의 팀이 참가 -> 팀은 1번부터 n번까지 번호가 매겨져 있다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다.
하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

입력

첫째 줄에는 테스트 케이스의 개수 (테스트 개수 ≤ 100)

• 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
• n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다. -> 작년 순위
• 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
• 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

출력

각 테스트 케이스에 대해 n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

순서대로 순위를 정렬한다는 점에서 위상정렬을 사용한다. 그러나 보통의 위상정렬과 다른점은 순위가 변동되기 때문에 이를 확인하는 방법이 있어야 한다는 점이다. -> 2차원 배열을 사용해서 작년 순위별로 저장한 후, 순위가 변동될 경우 반대로 바꿔준다.
또한 확실한 순위를 만들 수 없는 경우와 일관성이 없는 잘못된 경우도 찾아내야하는데, 사이클이 생기는 경우와 동일 진입차수가 여러개인 경우를 찾아내면 된다.

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

using namespace std;
int T,N,M;

int main(){
    cin>>T; //테스트 수
    
    for(int t=0;t < T; t++){
        cin>>N;
        int indegree[501]={0,}; //각 등수에 대한 진입차수 저장
        int arr[501]; //작년 순위 저장
        bool order[501][501]={false, }; //순위가 바뀌는 것을 확인하기 위해 자신보다 낮은 순위의 팀들 저장
        vector<int> result;
        int data;
        
        for(int i=0;i < N; i++){
            cin>>data;
            arr[i]=data;
            indegree[data]=i; //자신보다 낮은 순위를 모두 가리키도록 -> 1등: 진입차수 0, 2등:진입차수 1 ...
        }
        
        for(int i=0;i < N-1; i++){
            for(int j=i+1; j < N; j++){
                order[arr[i]][arr[j]]=true; //자신보다 등수가 낮은 팀 true
            }
        }
        
        cin>>M;
        int a,b;
        //순위 변동
        for(int i=0;i < M; i++){
            cin>>a>>b;
            if(order[a][b]){ //a가 b보다 등수가 높았던 경우
                indegree[a]++;
                indegree[b]--;
                order[a][b]=false;
                order[b][a]=true;
            }else{ //a가 b보다 등수가 낮았던 경우
                indegree[a]--;
                indegree[b]++;
                order[a][b]=true;
                order[b][a]=false;
            }
           
        }
        
        queue<int> q;
        for(int i=1;i<=N;i++){
            if(indegree[i]==0){ //진입차수가 0인경우 큐에 넣기
                q.push(i);
            }
        }
        
        bool cycle=false, check=true;
        
        for(int i=0;i<N;i++){ //위상정렬
            if(q.empty()){ //사이클이 발생한 경우
                cycle=true;
                break;
            }
            if(q.size()>=2){ //동일한 등수의 팀이 여러개인 경우
                check=false;
                break;
            }
            
            int cur=q.front();
            result.push_back(cur);
            q.pop();
            
            for(int j=1;j<=N;j++){
                if(order[cur][j]==true){
                    indegree[j]--;
                    if(indegree[j]==0){
                        q.push(j);
                    }
                }
            }
        }
        
        if(cycle==true){
            cout<<"IMPOSSIBLE\n";
        }
        else if(check==false){
            cout<<"?\n";
        }else{
            for(int i=0;i<N;i++){
                cout<<result[i]<<" ";
            }
            cout<<"\n";
        }
        
        
    }
    
    return 0;
}