[ 백준 / C++ ] 3665 : 최종 순위

[ 문제 ]

 

3665번: 최종 순위

 

[ 접근방법 ]

 

매 케이스마다 위상 정렬을 통해 팀 순서를 파악한다.

 

1. 작년 순위를 입력 받으면서 팀별 순서관계를 adj 배열에 저장한다.

2. 변동 순서관계를 입력 받아 adj를 반전시킨다.

3. 정리한 adj 배열을 바탕으로 위상 정렬을 실시한다. 이 때, dfs를 활용한다.

4. 정렬 결과에 역방향 간선이 있다면 팀 순위를 정할 수 없으므로 "IMPOSSIBLE"를 출력한다.

+. 모든 팀별 순서관계를 adj 배열에 저장하고 있기에 "?"를 출력할 경우는 존재하지 않는다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int tc, n, t[505], m, a, b;
bool adj[505][505], visited[505];
vector<int> ans;

void init()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            adj[i][j] = false;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        visited[i] = false;
    }

    ans.clear();
}

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

    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            adj[t[i]][t[j]] = true;
        }
    }

    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b;
        swap(adj[a][b], adj[b][a]);
    }
}

void dfs(int node)
{
    visited[node] = true;
    for (int i = 1; i <= n; i++)
    {
        if (adj[node][i] && !visited[i])
        {
            dfs(i);
        }
    }
    ans.push_back(node);
}

void topologicalSort()
{
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            dfs(i);
        }
    }

    reverse(ans.begin(), ans.end());

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (adj[ans[j]][ans[i]])
            {
                cout << "IMPOSSIBLE\n";
                return;
            }
        }
    }

    for (auto i : ans)
    {
        cout << i << " ";
    }
    cout << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> tc;
    while (tc--)
    {
        init();
        makeGraph();
        topologicalSort();
    }

    return 0;
}