[C++] 백준 3665: 최종 순위

문제 이해

- 대회에 여러 팀이 참여했다.

- 작년과 올해는 동일한 팀이 참여했으며, 작년의 전체 순위는 공개된다.

- 올해는 전체 순위는 발표되지 않으며, 작년에 비해 상대 순위가 바뀐 팀만 발표된다.

 

- n: 대회에 참가한 팀의 개수 (2 ~ 500, 10^2)

- m: 상대적인 등수가 바뀐 쌍의 수(0 ~ 25,000, 10^4)

 

출력

- 확실한 순위를 만들 수 없을경우: ? 출력

- 일관성이 없는 잘못된 정보 : IMPOSSIBLE 출력

- 확실한 전체 순위가 만들어질 경우: 1등 팀부터 차례대로 출력

 

 

 

문제 풀이

작년에 비해 상대 순위가 바뀐 팀에 대해 알려주므로 순서쌍이 주어지는 것으로 볼 수 있다.

즉, 위상 정렬을 사용하면 풀 수 있는 문제로 판단했다.

 

 

1. 선행 관계의 표현

 

하지만, 문제점이 있다.

작년의 전체 순위가 있을 때, 올해의 변동된 순서에 대해 어떻게 적용하면 좋을까...?

 

 

보통의 위상정렬은 벡터 배열을 통해 선행관계를 나타내는데,

이 문제는 도저히 그렇게 구현할 수가 없었다.

 

 

계속해서 벡터 배열을 통해 구현해보려 했지만, 쉽게 코드가 써지지 않아 결국 풀이를 보고 풀었다.

풀이에서는 bool형의 2차원 배열을 사용해서 선행 관계를 나타내었다.

 

bool order[505][505];

 

와 같이 2차원 배열을 선언했을 때,

order[a][b]: true일 경우, b팀 앞에 a팀이 와야한다는 뜻이다.

 

 

예제를 통해 살펴보자.

 

5 -> 4 -> 3 -> 2-> 1

와 같이 순서가 주어졌을 때,

 

order배열의 값은 다음과 같다.

	1	2	3	4	5
1
2	O
3	O	O
4	O	O	O
5	O	O	O	O

위의 표 중 제일 아래 행을 해석해보면

1, 2, 3, 4 팀 앞에 5팀이 와야 한다는 뜻이다.

 

이런 식으로 선행 관계를 표현하면 전체 순위가 주어졌을 때, 상대 순위가 변경되면 쉽게 표현할 수 있다.

 

 

2. 출력 조건의 해석

1) 확실한 순위를 만들 수 없을경우: ? 출력

2) 일관성이 없는 잘못된 정보 : IMPOSSIBLE 출력

3) 확실한 전체 순위가 만들어질 경우: 1등 팀부터 차례대로 출력

 

 

1) 확실한 순위를 만들 수 없을경우

이는 위상 정렬 도중 queue에 2개 이상의 값이 들어있을 경우 성립할 수 있다.

즉, 큐의 size가 2 이상이 되면 ? 출력하도록 하면 된다.

 

 

2) 일관성이 없는 잘못된 정보

일관성이 없다는 뜻은 순서를 제대로 파악할 수 없도록 순환 그래프가 만들어진다는 뜻이다.

 

순환 그래프의 판단은 위상 정렬이 끝났을 때,

(1) 정점에 들어가는 간선의 개수를 체크하는 방법

(2) 위상 정렬 후 정답이 들어있는 벡터의 사이즈를 체크하는 방법

등이 있는데 이 문제에서는 (2)를 통해 해결해보았다.

 

 

3) 확실한 전체 순위가 만들어질 경우

위상 정렬을 진행하며 정답 벡터에 큐에서 빼낸 값들을 넣어

정렬이 끝난 후 차례대로 출력해주었다.

 

 

 

이후 문제 조건을 다시 읽어보며 알게된 점인데,

작년의 전체 순위가 주어지고,

상대 순위가 바뀐 모든 팀의 정보가 주어지므로 사실상 1)의 경우는 성립할 수 없다.

그러므로, 1)은 코드상에 구현하지 않아도 좋다!

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int t;
bool order[505][505];
int ranking[505];
int inDegree[505];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>t;
    while(t--){
        //0. 초기화
        memset(order, false, sizeof(order));
        memset(ranking, 0, sizeof(ranking));
        memset(inDegree, 0, sizeof(inDegree));

        //1. 입력
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++){
            cin>>ranking[i];
        }
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++){
                order[ranking[i]][ranking[j]] = true;
            }
        }

        int m;
        cin>>m;
        for(int i = 0; i < m; i++){
            int a, b;
            cin>>a>>b;

            if(order[a][b]){
                order[b][a] = true;
                order[a][b] = false;
            }else{
                order[a][b] = true;
                order[b][a] = false;
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(order[i][j]){
                    inDegree[j]++;
                }
            }
        }

        //2. 위상정렬
        queue<int> q;
        for(int i = 1; i <= n; i++){
            if(inDegree[i] == 0) q.push(i);
        }

        vector<int> ans;
        while(!q.empty()){
            int now = q.front();
            q.pop();
            ans.push_back(now);
            
            // 순환을 피하기 위함.
            inDegree[now]--;

            for(int i = 1; i <= n; i++){
                if(order[now][i]) inDegree[i]--;
                if(inDegree[i] == 0) q.push(i);
            }
        }

        int size = ans.size();
        if(size == n){
            for(int i = 0; i < n; i++){
                cout<<ans[i]<<" ";
            }
            cout<<"\n";
        }else{
            cout<<"IMPOSSIBLE\n";
        }
    }
    
    return 0;
}

 

위상 정렬을 할 때 선행 관계의 표현을 벡터 배열이 아닌 인접 배열을 사용할 수도 있다는 정보를 알려준 좋은 문제였다!