[C++/3665] 최종 순위 - using 위상 정렬 (topology sort)

문제

 

아이디어: 위상 정렬

문제에서는 "순위"를 나열해야 하기 때문에 방향 그래프라는 것을 쉽게 알 수 있다. 이를 순위에 맞게 나열하는 것은 방향 그래프를 정렬하는 것과 같으므로 위상 정렬을 사용할 수 있다.

 

이때 사이클이 없는 위상 정렬은 항상 노드가 N개 일때 queue를 N번 돌기 때문에, 사이클이 생긴다면 N보다 작은 횟수로 종료하게 된다. 왜냐하면 진입 차수가 0이 되는 노드가 없어서 더 이상 탐색을 진행할 수 없기 때문이다. 따라서 이 경우 쉽게 "IMPOSSIBLE" 인 경우를 알 수 있다.

 

데이터의 일관성이 없는 경우 "?"를 출력하라고 하였는데 이는 같은 등수인 노드가 여러개인 경우이다. 이 오류는 queue에 들어간 node의 갯수가 몇개인지에 따라 알 수 있다. 즉 2개 이상의 node가 queue에 들어간 경우, 등수가 같다는 뜻이므로 오류가 발생한 것이다.

 

하지만 사실상 이 오류는 발생하지 않기 때문에 그냥 성공 아니면 IMPOSSIBLE을 출력해도 된다.

 

구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int indegree[501];

int topology(int v, vector<int> graph[501], vector<int> &result)
{
    queue<int> q;
    int limit = 0;
    
    for(int i = 1;i <= v;i++)
    {
        if (indegree[i] == 0)
        {
            q.push(i);
        }
    }
    
    while (!q.empty())
    {
        limit += 1;
        
        // queue의 사이즈가 2 이상인 경우
        // -> 즉 indegree가 0인게 2개라면 1등인 노드가 여러개라는 것이므로 순위를 알 수 없다. 즉 "?"인 경우임
        if (q.size() >= 2)
            return 2;
        
        int now = q.front();
        q.pop();
        
        result.push_back(now);
    
        for(int i = 0;i < graph[now].size();i++)
        {
       		// 진입 차수 낮추고 0이 되면 다시 queue에 넣기
            indegree[graph[now][i]] -= 1;
            
            if (indegree[graph[now][i]] == 0)
            {
                q.push(graph[now][i]);
            }
        }
    }
    // 성공
    if (limit == v)
        return 0;
    
    // 사이클이 생기면 impossible
    else
        return 1;
}
int main()
{
    // 테스트 케이스
    int T;
    cin>>T;
    
    while (T-- > 0)
    {
        // 연결 정보
        vector<int> graph[501];
        fill_n(indegree, 501, 0);
        
        // 팀의 수
        int n;
        cin>>n;
        
        vector<int> team;
        for(int i = 0;i < n;i++)
        {
            int temp;
            cin>>temp;
            
            team.push_back(temp);
        }
        
        
        for(int i = 0;i < team.size();i++)
        {
            for(int j = i + 1;j < team.size();j++)
            {
                graph[team[i]].push_back(team[j]);
                // 진입 차수 증가
                indegree[team[j]] += 1;
            }
        }

        // 변경된 수
        int m;
        cin>>m;
        
        vector<pair<int, int>> v;
        //bool stop = false;
        for(int i = 0;i < m;i++)
        {
            int a, b;
            cin>>a>>b;
            
            v.push_back({a, b});
        }

        for(int i = 0;i < v.size();i++)
        {
            // 올해가 a > b 라는 뜻
            int a = v[i].first;
            int b = v[i].second;
            
            // 순서 변경하고 넣기
            bool flag = false;
            for(int j = 0;j < graph[a].size();j++)
            {
                if (graph[a][j] == b)
                {
                    flag = true;
                    graph[a].erase(graph[a].begin() + j);
                    indegree[b] -= 1;
                }
            }
            if (flag == true)
            {
                graph[b].push_back(a);
                indegree[a] += 1;
            }
            else
            {
                for(int j = 0;j < graph[b].size();j++)
                {
                    if (graph[b][j] == a)
                    {
                        graph[b].erase(graph[b].begin() + j);
                        indegree[a] -= 1;
                    }
                }
                
                graph[a].push_back(b);
                indegree[b] += 1;
            }
        }


        vector<int> ans;
        
        int result = topology(n, graph, ans);
        
        // 실패 -> impossible(사이클 생성)
        if (result == 1)
            cout<<"IMPOSSIBLE"<<endl;
        
        // 실패 -> 데이터 일관성 없는 경우
        else if (result == 2)
            cout<<"?"<<endl;
        
        // 성공
        else
        {
            for(int i = 0;i < ans.size();i++)
                cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}