[백준] 3665번 최종순위

3665 최종순위

문제

---

올해 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"을 출력한다.

---

풀이)

위상정렬(Topology sort)을 이용해 순위 순서대로 출력하는 문제이다.

과정

1. 작년의 등수를 기반으로 

   인접 행렬 int adj[][]을 이용해 간선들을 연결시켜준다.

   adj[i][j] = 1 // i에서 j까지 가는 간선이 존재 = i는 j보다 등수가 높다.

   (인접리스트가 아닌 인접행렬을 이용하는 이유는 나중에 상대적인 등수가 바뀌였을 때, 

     간선 연결방향을 바꾸기 용이하게 하기 위해서이다.) 

    그리고 간선을 연결시킬때, 연결 당한 입장 팀의 진입 차수를 저장하는 배열 int indegree[]의 값도 증가시켜 준다.

   indegree[j]++; //j를 향해 들어가는 간선의 개수 1증가

  

 *주의*  순위가 5->4->3 일때 adj[5][4], adj[4][3] 뿐만이 아니라 adj[5][3]도 1로 바꿔줘야한다.(간선을 연결시켜줘야한다.)

2. 상대적인 등수가 바뀌는 m번 쌍의 수를 이용해, 간선 방향과 indegree 개수를 변화시켜준다.

   ex)    (a,b) //a와 b의 상대적인 등수를 바꿔라

a가 등수가 b보다 높을 경우? adj[a][b] == 1 일때

a가 등수가 b보다 낮을 경우? adj[b][a] == 1 일때

각각의 경우에서 서로 간선의 방향을 바꿔주고, 간선의 방향을 바꿔줬으니 진입차수의 개수도 바꿔준다.

3. 인접 행렬과 진입 차수 저장 배열을 이용해 위상정렬을 수행한다.

   (위상정렬은 queue를 이용해 구현하였다.)

  * 위상정렬에서 총 팀의 개수인 n번의 계산을 수행하는데,

    계산 도중 queue의 size == 0일 경우, 즉 비었을 경우는 그래프 내에 사이클이 존재한다는 뜻이니깐

    제대로 순위를 매기지 못하는 것이다. => 바로 실패, IMPOSSIBLE 출력

    

    계산 도중 queue의 size >= 2일 경우, 즉 queue에 하나의 원소가 아닌 여러개의 원소가 들어왔을 경우는 

    순위의 정답이 여러개 존재한다는 뜻이니깐 확실히 순위를 매기지 못하는 것이다 => 바로 실패, ? 출력

코드)

#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
 
int n, m,a, b;
int score[501]; // 작년 순위를 저장하는 배열 & 올해 순위를 저장하는 배열
bool adj[501][501]; // 상하관계를 나타내는 배열
int indegree[501]; // 진입차수를 저장하는 배열
int main() {
    int test_case;
    scanf("%d", &test_case);
    while (test_case--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &score[i]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                adj[score[j]][score[i]] = 1;
                indegree[score[i]]++;
            }
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &a, &b);
            if (adj[a][b]) {//a의 등수가 b의 등수보다 높았을때
                indegree[a]++;
                indegree[b]--;
                adj[a][b] = 0;
                adj[b][a] = 1;
            }
            else {
                indegree[a]--;
                indegree[b]++;
                adj[a][b] = 1;
                adj[b][a] = 0;
            }
        }
 
        queue <int> qu;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) qu.push(i);
        }
        int fail = 0;
        for (int i = 1; i <= n; i++) {//위상정렬 n번의 정점만 진행
            if (qu.empty()) {//n번 진행하기도 전에 queue가 비었다 -> cycle존재, 순위를 정할 수 없음
                fail = 1;
                break;
            }
            else if (qu.size() >= 2) {//queue의 size가 두개이상 -> 순서를 정확히 하기 힘듬, 답이 여러개
                fail = 2;
                break;
            }
 
            int here = qu.front();
            qu.pop();
            score[i] = here;//score 배열 재사용-> 원래는 작년 순위를 저장하는 배열이었음
            for (int j = 1; j <= n; j++) {
                if (adj[here][j]) {
                    indegree[j]--;
                    if (indegree[j] == 0) {
                        qu.push(j);
                    }
                }
            }
        }
 
        if (fail == 1) {
            printf("IMPOSSIBLE\n");
        }
        else if(fail == 2){
            printf("?\n");
        }
        else {
            for (int i = 1; i <= n; i++) {
                printf("%d ", score[i]);
            }
            printf("\n");
        }
 
        //다음 test_case를 위해 초기화
        memset(adj, 0, sizeof(adj));
        memset(indegree, 0, sizeof(indegree));
        memset(score, 0, sizeof(score));
    }
 
 
    return 0;
}