BOJ 백준 3665번 최종순위

BOJ 백준 3665 최종순위

문제: www.acmicpc.net/problem/3665

3665번: 최종 순위

1번부터 n번까지 번호가 매겨진 팀들이 작년과 올해 대회에 참전했는데, 문제에서 알려주는 데이터는 작년 대회에서의 최종 순위와 올해 대회에서 상대적인 순위가 바뀐 팀들의 목록이다. 이를 바탕으로 올해 최종 순위를 구해야 하는데, 최종 순위가 완성될 수 없는 경우도 고려해야 한다. 이와 같은 경우는 다음과 같다.

 

 

 

1) 데이터의 일관성이 없는 경우

 

 

2) 확실한 순위를 찾을 수 없는 경우

 

 

 

최종 순위가 완성될 수 있으면 이는 위상 정렬로 문제를 풀 수 있는 조건을 만족한다. 각 팀은 정점으로 나타낼 수 있고, 순위가 낮은 곳에서 높은 곳으로 정점 간 간선을 이어 줄 수 있으며, 최종 순위 완성이 가능함은 그래프로 나타냈을 때 cycle이 존재하지 않음을 의미하기 때문이다. 따라서 directed acyclic graph로 표현이 가능하므로 완성 조건에 위배되지만 않으면 위상 정렬로 간단히 풀 수 있는 문제이다. 위상 정렬 알고리즘은 DFS 방문 순서를 역전하는 방법과 정점의 indegree와 queue를 이용한 BFS를 사용하는 방법이 있는데, 여기서는 최종 순위가 완성될 수 없는 경우를 고려하여 후자를 택했다. (Directed graph에서 DFS를 통해 cycle을 찾을 수 있지만, DFS로 확실한 순위를 찾을 수 없는 경우는 알아낼 수 없다.)

 

그러나 고려해야 할 점은 문제의 입력 데이터가 최종 순위 완성이 불가능할 수도 있고, 이를 알아내서 결과를 출력해야 한다는 것이다. 데이터의 일관성이 없다는 건 위상 정렬 그래프로 나타냈을 때 그래프 내 cycle이 존재한다는 것이고, 확실한 순위를 찾을 수 없다는 건 위상 정렬을 했을 때 둘 이상의 정점의 정렬 순위가 서로 달라질 수 있음을 의미한다. 

 

 

 

처음에는 이를 해결하고자 정점의 outdegree를 사용하여 cycle의 존재 여부를 구하려고 했지만 논리적인 오류가 있음을 알았다.

outdegree가 0인 정점이 없다 → 데이터의 일관성이 없다 (O)

이유: outdegree가 0인 정점이 없다 → 모든 정점이 cycle에 속한다 → 데이터의 일관성이 없다.

 

 

그렇지만 아래는 틀리다.

outdegree가 0인 정점이 있다 → 데이터의 일관성이 있다 (X)

이유: outdegree가 0인 정점이 있어도 다른 정점 집합에 cycle이 존재할 수 있다. (위 정리 노트 그림 참조)

 

 

 

따라서 BFS를 사용한 위상 정렬 과정에서 최종 순위를 완성할 수 없는 경우를 같이 처리해야 한다. 이를 정리하면 다음과 같다.

 

 

1) 데이터의 일관성이 없는 경우 ↔ cycle이 존재하는 경우 ↔ 위상 정렬 과정에서 방문하는 정점의 수가 n개보다 작다

이유: 위상 정렬 그래프에서 cycle이 있으면 cycle을 이루는 정점은 BFS 위상 정렬 과정에서 indegree가 0이 될 수 없으므로 queue에 push 될 수 없다.

 

 

2) 확실한 순위를 찾을 수 없는 경우 ↔ 위상 정렬 시 둘 이상의 정점의 정렬 순위가 서로 달라질 수 있는 경우 ↔ BFS 위상 정렬 과정에서 indegree가 서로 같은 정점이 있는 경우 ↔ BFS 위상 정렬 시 queue에 두 개 이상의 정점이 들어간다

 

 

이를 바탕으로 아래 코드를 작성했다.

 

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int N_MAX = 500;

int t, n, m;
int indegree[N_MAX + 1];
bool edges[N_MAX + 1][N_MAX + 1];

int main(){
    scanf("%d", &t);
    while(t--){
        memset(indegree, 0, sizeof(indegree));
        memset(edges, false, sizeof(edges));
        scanf("%d", &n);
        vector<int> v;
        for (int i = 0; i < n; i++){
            int x; scanf("%d", &x);
            for (auto y: v){
                edges[x][y] = true;
                indegree[y] += 1;
            }
            v.push_back(x);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++){
            int a, b;
            scanf("%d %d", &a, &b);
            if (edges[a][b]){
                edges[a][b] = false;
                indegree[b] -= 1;
                edges[b][a] = true;
                indegree[a] += 1;
            }
            else if (edges[b][a]){
                edges[b][a] = false;
                indegree[a] -= 1;
                edges[a][b] = true;
                indegree[b] += 1;
            }
        }
        
        // Topological Sort
        queue<int> q;
        
        bool isVague = false;
        
        for (int i = 1; i <= n; i++){
            if(!indegree[i]) {
                q.push(i);
            }
        }
        
        vector<int> ans;
        
        while(!q.empty()) {
            if (q.size() > 1){
                isVague = true;
            }
            int cur = q.front();
            ans.push_back(cur);
            q.pop();
            
            for (int next = 1; next <= n; next++){
                if (!edges[cur][next]) continue;
                indegree[next] -= 1;
                if (!indegree[next]){
                    q.push(next);
                }
            }
        }
        

        if (ans.size() != n){
            printf("IMPOSSIBLE\n");
            continue;
        }
        
        if (isVague){
            printf("?\n");
            continue;
        }
        
        reverse(ans.begin(), ans.end());
        
        for (auto x: ans){
            printf("%d ", x);
        }
        printf("\n");
    }
    
    return 0;
}