백준) 3665 최종 순위

최종 순위

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

기존 위상이 주어지고, 노드끼리의 위상을 뒤바꿨을 때, 새롭게 위상들이 잘 정렬되는지 확인해야 하는 문제다.

따라서 그래프를 잘 정의해서 위상이 뒤바뀜을 잘 데이터로 표현해야 한다.

위상이 뒤바뀌면 그래프에선 무슨 일이 생길까?

주의할 점은 두 노드끼리의 위상순서만 바꾸는 것이지, 다른 노드들와의 위상순서는 그대로야 한다는 점이다.

첫번째 테스트 케이스를 보면 위상순서는 5 < 4 < 3 < 2 < 1 이다.

이후 2와 4 // 3과 4의 위상순서를 바꾸라고 한다.

기존의 위상비교는 2 > 4 // 3 > 4 였으니, 2 < 4 // 3 < 4로 바꿔야 한다.

이 때 기존의 위상비교, 예를 들어 5 < 4 나 3 < 1 같은 순서는 바뀌면 안되는 것이다.

그래프에선 간선만 휘까닥 뒤집어주면 된다. 애초에 a->b로 진출하는 간선이었다면,

이는 명확히 위상순서가 a<b임을 나타내고 있다.

따라서 간선만 a<-b로 바꿔주면 기존의 위상순서를 지키면서 바꿔줄 수 있다.

이제 그래프를 무엇으로 표현할지 생각해보자.

인접리스트로 표현한 그래프라면 뒤집어야 할 해당간선을 찾는데 해당 리스트를 전부 뒤져야 한다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 그냥 리스트 전부를 보면 되는데 간편함이 있다.

반면 인접행렬로 표현한 그래프라면 뒤집어야 할 해당간선을 바로 찾을 수 있음에 이점이 있다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 해당 행을 전부 봐야하는데 단점이 있다.

큐질에서 어차피 둘 다 O(n)이므로 인접행렬로 하자.

주의할 점은 기존 순위로 간선을 만들 때에, 5->4->3->2->1로 간선 4개만 만드는게 아니라,

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

4->3, 4->2, 4->1

3->2, 3->1,

2->1

모든 간선을 만들어줘야 한다는 점이다. 이래야 나중에 간선을 뒤집을 때에 기존 위상순서를 유지할 수 있다.

정답은 세 가지로 분류되는데, 확실한 순위가 정해지든지(1), 순위가 안정해지든지(2), 데이터에 일관성이 없든지(3) 세 가지다.

(1)은 위상정렬이 완료되면 당연한 결과다.

(2)는 테크트리가 완료되는 노드가 동시에 2개 이상 생긴다는 뜻으로, 큐에 2개 이상의 노드가 들어가는 결과다.

(3)은 사이클이 생긴다는 의미로, 위상정렬 완료뒤에도 정렬되지 않은 노드가 남아있는 결과다.

#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
 
int tc, n, m, a, b;
int mat[501][501], order[501], in[501];
 
int main() {
    scanf("%d", &tc);
    while (tc--) {
        memset(mat, 0, sizeof(mat));
        memset(in, 0, sizeof(in));
 
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &order[i]);
 
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                mat[order[i]][order[j]] = 1;
                in[order[j]]++;
            }
        }
 
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &a, &b);
            if (mat[a][b]) {
                mat[a][b] = 0;
                mat[b][a] = 1;
                in[b]--, in[a]++;
            }
            else {
                mat[b][a] = 0;
                mat[a][b] = 1;
                in[a]--, in[b]++;
            }
        }
 
        queue<int> q;
        for (int i = 1; i <= n; ++i)
            if (!in[i])
                q.push(i);
 
        bool certain = true;
        vector<int> ans;
        while (!q.empty()) {
            if (q.size() > 1) {
                certain = false;
                break;
            }
 
            int cur = q.front();
            q.pop();
            ans.push_back(cur);
 
            for (int next = 1; next <= n; ++next) {
                if (mat[cur][next]) {
                    in[next]--;
                    if (!in[next])
                        q.push(next);
                }
            }
        }
 
        if (!certain) //uncertain
            puts("?");
        else if (ans.size() == n) { //possible
            for (int i = 0; i < n; ++i)
                printf("%d ", ans[i]);
            puts("");
        }
        else //impossible
            puts("IMPOSSIBLE");
    }
    return 0;
}