[Beakjoon] 3665 최종 순위 (C++)

문제 링크

BOJ 3665 : 최종 순위

문제

• N개의 팀과 해당 팀들의 작년 순위가 주어진다.
• M개의 관계가 주어진다.
  * a b 가 주어졌을 때 해당 팀의 순위 관계가 역전되었음을 의미한다.
• 역전된 관계를 적용하여 올해 순위를 출력한다.

풀이

주의할 점

• 관계가 역전된 것을 제외하면 모든 팀들은 작년 순위 관계를 유지해야한다.
• a b가 주어졌을 때 먼저 나온 팀이 순위가 더 높아야함을 의미하는 것이 아니다. 두 팀의 관계가 역전되었음을 의미하는 것이다.

N의 크기가 크지 않다. 작년 순위관계를 모두 위상정렬의 고려사항에 추가하여 문제를 해결해야 한다.

관계가 역전된 경우 기존 위상정렬 관계를 제거하고 다시 재정의 한다.

애매하게 효율적으로 해보겠다고 한참 고민했는데 가끔은 그냥 우직하게 find같은 함수를 써줘야 할 필요가 있는 것 같다.

코드

#include<bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

int A[505];
int GRADE[505];

void Solve() {
    int N,M; 
    cin>>N;
    
    for(int i=1; i<=N; i++) {
        cin>>A[i]; GRADE[A[i]] = i;
    }
    
    vector<int> G[N+1]; 
    
    cin>>M;
    int a,b; 
    int BF[N+1]; memset(BF, 0, sizeof(BF));

    for(int i=1; i<=N; i++){
        for(int j=i+1; j<=N; j++){
            G[A[i]].push_back(A[j]);
            BF[A[j]]++;   
        }
    }

    for(int i=0; i<M; i++){
        cin>>a>>b;
        if(GRADE[a]>GRADE[b]){
            G[b].erase(find(G[b].begin(), G[b].end(), a));
            G[a].push_back(b);
            BF[b]++; BF[a]--;
        }
        else {
            G[a].erase(find(G[a].begin(), G[a].end(), b));
            G[b].push_back(a);
            BF[a]++; BF[b]--;    
        }
    }
    
    
    
    vector<int> ANS;
    queue<int> Q;
    for(int i=1; i<=N; i++){if(BF[i]==0) Q.push(i);}
    if(Q.size()>1) {cout<<"IMPOSSIBLE"; return;}
    while(!Q.empty()){
        int n = Q.front(); Q.pop();
        ANS.push_back(n);

        for(int i=0; i<G[n].size(); i++){
            if(--BF[G[n][i]]==0) Q.push(G[n][i]);
        }
    }

    if(ANS.size()==N) {
        for(int n: ANS) cout<<n<<" ";
        cout<<endl;
    } else cout<<"IMPOSSIBLE"<<endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T; cin>>T;
    while(T-->0){
        Solve();
    }
    return 0;
}

!!