[백준] 최종 순위_3665

위상 정렬을 공부했었지만 다시 까먹어버렸다. 이 문제는 위상정렬 문제라는 것을 모르고 풀고 있었다.

주의해야 할 점은 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어진다는 것이다. 상대적인 순위가 바뀐 것이지 팀1 팀2 이렇게 주어졌을 때 팀1이 팀2보다 순위가 높다는 말은 아니다.

2
1 2
1
1 2

따라서 다음 테스트케이스에서 답은 2 1 이 나와야 한다. 기존 1 2 의 순위가 바뀌어서 2 1 이 되었으므로.

 

같은 순위를 가지는 팀은 없으므로 이긴 횟수(어떤 팀이 다른 팀보다 순위가 높다면 이겼다고 보고)와 등수는 직결된다. 

ex) 팀이 6개라면 
1번 이겼으면 5등 
5번 이겼으면 1등 

 

하지만 이런 방법으로는 확실하지 않은 순위는 중복된 순위가 나올 것이므로 처리할 수 있겠지만, 데이터의 일관성은 체크할 수 없었다... 애초에 그래프로 접근해야 하는 문제였다. 데이터의 일관성은 사이클의 유무를 보면 된다. 

 

위상정렬을 이용하는 방법은 a팀보다 b팀이 순위가 높은 것을 a에서 b로 들어가는 차수가 있다는 것으로 표현하면 된다. 

 

1) 위상정렬이 정상적으로 된 경우 

노드 n개가 모두 result queue에 들어간 경우

 

2) 확실하게 순위를 정할 수 없는 경우 

한 번에 큐에 두 개가 들어간다면 진입 차수가 0인 노드가 여러개라는 소리로, 확실한 순위를 얻을 수 없다. 

occidere님 블로그 예시에서, 2 3 4 는 초기에 진입 차수가 0이었던 대학 입학을 없앤 후 봤을 때 모두 진입차수가 0이 되므로, 이들끼리의 순서는 확실하게 정할 수 없다.  

이 문제에서는 진입 차수가 0인 노드가 한 개 이상이라면 확실하게 순위를 정할 수 없으므로 탐색을 그냥 끝내면 된다. 

 

3) 데이터에 일관성이 없는 경우 

사이클이 있는지를 체크하면 된다. 

result에 노드를 넣으려면 진입 차수가 0이어야 한다. 하지만 사이클이 있게 된다면 어떤 노드에서도 진입 차수는 1 이상이게 된다. 

 

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
 
int test, n, t, m, a, b;
int mat[501][501], order[501], indegree[501];
 
int main() {
    cin >> test;
    while (test--) {
        memset(mat, 0, sizeof(mat));
        memset(indegree, 0, sizeof(indegree));
        queue<int> q;
        queue<int> result;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> order[i];
        }
        //순위 - 인접 행렬 형식으로 그래프 생성, 진입차수 기록
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                mat[order[i]][order[j]] = 1;
                indegree[order[j]]++;
            }
        }
        //상대적인 순위가 바뀐 경우 계산
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> a >> b;
            if (mat[a][b]) {
                mat[a][b] = 0; 
                mat[b][a] = 1;
                indegree[a]++;
                indegree[b]--;
            }
            else {
                mat[b][a] = 0;
                mat[a][b] = 1;
                indegree[a]--;
                indegree[b]++;
            }
        }
        //진입 차수가 0인 노드들을 큐에 저장 
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) q.push(i);
        }
        bool certain = true;
        while (!q.empty()) {
            if (q.size() > 1) {
                certain = false;
                break;
            }
            int node = q.front();
            q.pop();
            result.push(node);
            for (int i = 1; i <= n; i++) {
                if (mat[node][i]) { //진입 경로가 있다면 
                    indegree[i]--;
                    if (indegree[i] == 0) q.push(i);
                }
            }
        }
        if (certain == false) cout << "?\n";
        else if (result.size() != n) cout << "IMPOSSIBLE\n";
        else {
            while (!result.empty()) {
                int node = result.front();
                result.pop();
                cout << node << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}