[BOJ알고리즘, C++]#3665_최종 순위, 그래프, 위상 정렬, 진입 차수 BFS

 

#1. 문제

 

3665번: 최종 순위

 

---

 

#2. 풀이

 

1. 그래프

 

[자료구조]#6_그래프

 

그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 그래프 자료구조의 노드 간 연결 관계는 간선으로 나타내며, 간선의 방향성, 연결 강도를 통해 다양한 형태로 나타낼 수 있습니다.

 

2. 위상 정렬

 

[자료구조]#6_그래프

 

위상 정렬은 비순환 유향 그래프(DAG)에서 각 정점들의 선행 관계를 유지하며 정점을 나열하는 방법입니다. 일반적으로, 위상 정렬 알고리즘은 재귀 호출 DFS 혹은 진입 차수 BFS를 활용하여 구현 가능합니다.

 

3. 랭킹이 높은 친구는 다른 모든 랭킹이 더 낮은 친구들 사이에 간선을 갖는다!

 

1. 먼저, 작년 순위 표를 입력받고, 이를 통해 작년 랭킹이 더 높은 친구들과 이보다 낮은 랭킹을 갖는 친구들 사이에 간선을 추가해 줍니다. 물론, 더 높은 랭킹 친구가 시작점, 그리고 더 낮은 랭킹 친구가 도착점으로 간선의 "방향성"을 설정하는 게 중요합니다.(위상 정렬 알고리즘은 DAG만 가능합니다!)
2. 그리고, 순위가 바뀐 친구들의 간선 방향을 역 방향으로 변경해 줍니다.
3. 다음으로, 최종 그래프에 대하여 위상 정렬을 수행하고, 모든 정점이 포함되지 않을 경우, 순위 예측이 불가능한 것으로 판단하고, 반대로 모든 정점이 위상 정렬 결과 값에 포함된다면, 해당 순위 예측을 결과로 출력해 줍니다!

 

---

 

#3. 코드

 

/*
    문제 : 바뀐 순위, 일관성 및 가능성 확인
    설명
            1. 먼저, 윗 랭크 정점은 그보다 아래 있는 랭크 정점과 모두 간선을 갖는다.
            2. 순위가 바뀐 정점 쌍 끼리 간선 방향을 바꾸고, 진입 차수 값을 변경한다.
            3. 위상 정렬을 수행하고, 정상적으로 모든 정점이 순서를 가지면 성공, 아니면 실패
*/

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

#define NO_ANSWER "IMPOSSIBLE"

int T, n, m;

void TopologicalSort(vector<vector<int>> &adjMatrix, vector<int> &InDegree)
{
    // 큐 자료구조
    queue<int> q;
    vector<int> res;
    // 진입차수 0인 정점을 큐에 삽입
    for (int i = 1; i <= n; ++i)
    {
        if (InDegree[i] == 0)
            q.push(i);
    }

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        res.push_back(cur);

        for (int neighbor = 1; neighbor <= n; ++neighbor)
        {
            if (!adjMatrix[cur][neighbor])
                continue;

            if (--InDegree[neighbor] == 0)
            {
                q.push(neighbor);
            }
        }
    }

    if ((int)res.size() == n)
    {
        for (int i = 0; i < (int)res.size(); ++i)
            cout << res[i] << ' ';

        cout << '\n';
    }
    else
    {
        cout << NO_ANSWER << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while (T--)
    {
        cin >> n;

        vector<int> lastYear(n + 1);
        vector<vector<int>> adjMatrix(n + 1, vector<int>(n + 1));
        vector<int> InDegree(n + 1, 0);

        for (int i = 1; i <= n; ++i)
        {
            cin >> lastYear[i];
        }

        for (int i = 1; i <= n; ++i)
        {
            int curNode = lastYear[i];
            for (int j = i + 1; j <= n; ++j)
            {
                int nextNode = lastYear[j];
                adjMatrix[curNode][nextNode] = 1;
                InDegree[nextNode]++;
            }
        }

        cin >> m;

        for (int i = 0; i < m; ++i)
        {
            int u, v;
            cin >> u >> v;

            if (adjMatrix[u][v])
            {
                adjMatrix[u][v] = 0;
                adjMatrix[v][u] = 1;

                InDegree[u]++;
                InDegree[v]--;
            }
            else
            {
                adjMatrix[v][u] = 0;
                adjMatrix[u][v] = 1;

                InDegree[v]++;
                InDegree[u]--;
            }
        }
        TopologicalSort(adjMatrix, InDegree);
    }

    return 0;
}

 

---