최종 순위

알고리즘 구분 : 그래프 이론, 위상 정렬

문제

올해 ACM-ICPC 대전 인터넷 예선에는 총 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"을 출력한다.
예제 입력 1
3
5
5 4 3 2 1
2
2 4
3 4
3
2 3 1
0
4
1 2 3 4
3
1 2
3 4
2 3
예제 출력 1
5 3 2 4 1
2 3 1
IMPOSSIBLE

문제 풀이

일단 어려웠던 점은 m줄 동안 입력받은 상대적인 등수가 바뀌는 정보에 대하여 어떻게 처리해야 할 것인지에 대한 고민이 많았다. 이뿐만 아니라, 확실한 순위를 찾을 수 없다면 "?"를 출력하라고 하는데, 이에 대한 테스트케이스는 무엇이 있을지 생각하는 것 역시 어려웠다.

그래서 일단 구현해서 제출해보자라는 마인드로 구현을 시작했다.

위상정렬 알고리즘에 기반하여 문제를 풀었다.
예제를 통해 내가 푼 방식을 설명하자면,

• 첫 번째 테스트 케이스 (Idx : 팀 번호, Ind : 진입차수)
  (1) 상대적 등수가 바뀌기 전
  Idx 1 2 3 4 5
  Ind 4 3 2 1 0
  (2) 등수 바뀌기 : 2 4
  Idx 1 2 3 4 5
  Ind 4 2 2 2 0
  (3) 등수 바뀌기 : 3 4
  Idx 1 2 3 4 5
  Ind 4 2 1 3 0

-> 마지막 등수 바뀌기 이후 정리된 진입 차수를 기반으로 위상정렬 시행 : 5 3 2 4 1

• 세 번째 테스트 케이스 (Idx : 팀 번호, Ind : 진입차수)
  (1) 상대적 등수가 바뀌기 전
  Idx 1 2 3 4
  Ind 0 1 2 3
  (2) 등수 바뀌기 : 1 2
  Idx 1 2 3 4
  Ind 1 0 2 3
  (3) 등수 바뀌기 : 3 4
  Idx 1 2 3 4
  Ind 1 0 3 2
  (4) 등수 바뀌기 : 2 3
  Idx 1 2 3 4
  Ind 1 1 2 2

-> 마지막 등수 바뀌기 이후 정리된 진입 차수에서 시작할 수 있는 진입차수 존재하지 않기에, 순위를 정할 수 없는 경우이므로 "IMPOSSIBLE" 출력

의문점

문제에선 "?"의 경우에 대한 출력도 얘기하고 있는데, "?"는 잘 모르겠어서 일단 "IMPOSSIBLE"만 생각하고 만들어서 제출했는데 AC를 받았다. 이 부분에 대한 답을 아직 얻지 못했다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int tc, n, m;
int lastRank[501];
int indigree[501];
void topologySort();

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

    cin >> tc;
    while(tc--) {
        memset(lastRank, 0, sizeof(lastRank));
        memset(indigree, 0, sizeof(indigree));

        cin >> n;
        for(int i = 1; i < n + 1; i++) {
            int input;
            cin >> input;
            lastRank[input] = i;
            indigree[input] = i - 1;
        }

        cin >> m;
        for(int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            if(lastRank[a] < lastRank[b]) {
                indigree[a]++;
                indigree[b]--;
            }
            else {
                indigree[a]--;
                indigree[b]++;
            }
        }

        topologySort();
    }

    return 0;
}

void topologySort() {
    queue<int> q;
    vector<int> result;

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

    while(!q.empty()) {
        if(q.size() != 1) {
            cout << "IMPOSSIBLE" << endl;
            return ;
        }

        int now = q.front();
        q.pop();

        result.push_back(now);

        for(int i = 1; i < n + 1; i++) {
            indigree[i]--;

            if(indigree[i] == 0) {
                q.push(i);
            }
        }

    } 

    if(result.size() == n) {
        for(auto now : result) {
            cout << now << " ";
        }

        cout << endl;
    }
    else {
        cout << "IMPOSSIBLE" << endl;
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/3665
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.