[3665번] 최종 순위

문제 출처 :

https://www.acmicpc.net/problem/3665

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬(Topological Sort) :: http://www.crocus.co.kr/716

위상 정렬을 통해 해결 할 수 있는 문제이다.

이 문제에서 입력에서 오해하지 말아야 할 점은 예제를 통해 보면

4
1 2 3 4
3
1 2
3 4
2 3

에서 

처음에 1 2 3 4 순위로 정해져있는 것 그 자체를 위상 정렬을 위해 추가시키고

그 후 1 2, 3 4, 2 3은 1->2 , 3->4 ,2->3이 아니고 

1이 2보다 앞섰었다면 2->1로 바꾸고 2가 1보다 앞섰었다면 1->2로 바꾸는 것이다. 

결국 1과 2의 순위를 스왑해라는 의미이다.

이렇게 위상 정렬 전, 간선의 상태, 들어오는 간선의 수만 잘 조절해주면

그 다음부터는 위상 정렬 알고리즘을 이용하여 해결해 줄 수 있다.

마지막에 큐가 0이면 사이클이 존재하는 것이고, 

큐가 2이상이면 큐에서 사실 어느 것이 먼저 빠져도 위상 정렬이 되기에 정확한 순위를 알 수 없다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
 
#define swap(a,b){int t = a; a = b; b = t;}
 
using namespace std;
 
int arr[501];
int line[501];
int result[501];
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        int n;
        scanf("%d", &n);
 
        vector<int> vc[501];
        memset(arr, 0, sizeof(arr));
        memset(line, 0, sizeof(line));
        memset(result, 0, sizeof(result));
 
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
 
        // 기존에 있는 등수를 위상 정렬에 이용한다.
        int prev, cur;
 
        for(int i = 1; i <= n - 1; i++)
        {
            prev = arr[i];
 
            for (int j = i + 1; j <= n; j++)
            {
                cur = arr[j];
                line[cur]++;
 
                vc[prev].push_back(cur);
            }
        }
 
        int m;
        scanf("%d", &m);
 
        for (int i = 1; i <= m; i++)
        {
            scanf("%d %d", &prev, &cur);
 
            // prev와 cur의 순위가 바뀌는데
            // 어느것이 원래 앞에 있고 뒤에 있는지 모르니
            // chk를 통해 확인해낸다.
            bool chk = false;
            for (int j = 0; j < vc[prev].size(); j++)
            {
                // 만약 prev가 앞에 있었다면
                // cur이 이제는 순위가 더 앞선다는 의미
                if (vc[prev][j] == cur)
                {
                    // cur의 들어오는 간선을 지우고 prev의 간선을 늘린다.
                    line[cur]--;
                    line[prev]++;
 
                    // cur에 prev를 추가하고, prev에 cur을 지운다.
                    vc[cur].push_back(prev);
                    vc[prev].erase(vc[prev].begin() + j);
 
                    // 순위가 어디가 앞섰는지 알아냈으니 다음 for문은 못돌리게 한다.
                    chk = true;
                    break;
                }
            }
 
            if(chk == false)
            {
                for (int j = 0; j < vc[cur].size(); j++)
                {
                    // 만약 cur이 앞에 있었다면
                    // prev가 이제는 순위가 더 앞선다는 의미
                    if (vc[cur][j] == prev)
                    {
                        // prev의 들어오는 간선을 지우고 cur의 간선을 늘린다.
                        line[prev]--;
                        line[cur]++;
                        
                        // prev에 cur를 추가하고, cur에 prev를 지운다.
                        vc[prev].push_back(cur);
                        vc[cur].erase(vc[cur].begin() + j);
                        break;
                    }
                }
            }
        }
        
        queue<int> q;
        // 들어오는 간선이 없는 노드를 먼저 큐에 추가
        for (int i = 1; i <= n; i++)
            if (line[i] == 0)
                q.push(i);
 
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            // 큐가 비어있다면 사이클
            if (q.empty())
            {
                flag = 1;
                break;
            }
 
            // 큐가 2이상이라면 어느것이 먼저 뽑혀도 위상 정렬이 되기에
            // 순서를 정확히 알 수 없다.
            else if (q.size() >= 2)
            {
                flag = 2; 
                break;
            }
 
            int here = q.front();
            q.pop();
 
            result[i] = here;
 
            for (int j = 0; j < vc[here].size(); j++)
            {
                int there = vc[here][j];
 
                if (--line[there] == 0)
                    q.push(there);
            }
        }
 
        if (flag == 0)
            for (int i = 0; i < n; i++)
                printf("%d ", result[i]);
 
        else if (flag == 1)
            printf("IMPOSSIBLE");
 
        else if (flag == 2)
            printf("?");
 
        printf("\n");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>