[백준] 3665 최종 순위

3665번: 최종 순위

 

boj.kr

풀이

위상 정렬을 사용해서 해결할 수 있는 문제이다. 이 문제에서 핵심 아이디어는 작년의 순위를 가지고 유향 그래프를 만드는 것이다. 예제에서 첫 번째 테스트 케이스를 보면 5 4 3 2 1 순서로 순위가 결정되었는데, 이 말은 5번 팀은 1, 2, 3, 4번 팀보다 앞서있다는 의미이고, 4번 팀은 1, 2, 3번 팀보다 앞서있다는 의미, ... , 2번 팀은 1번 팀보다 앞서있다는 의미이다. 따라서 이 관계를 이용해서 유향 그래프를 생성할 수 있게 된다. 그리고 올 해에 변경된 팀들은 방향을 바꿔주면 된다. 그리고 바뀐 유향 그래프를 가지고 위상 정렬을 수행하면 해결할 수 있다.

코드

C++

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

int n, m;
vector<vector<bool>> adj;
vector<int> ranking;
vector<int> in_degree;

void topological_sort() {
    vector<int> result;

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0)
            q.push(i);
    }

    bool is_cycle = false;
    bool is_certain = true;

    /*
    위상 정렬을 정점의 개수만큼 반복한다
    (한번에 한 정점만 큐에 들어가야지 확실한 등수가 나오기 때문에)
    */
    for (int i = 0; i < n; i++) {
        // 반복문이 끝나기 전에 큐가 비었다는 것은 사이클이라는 의미
        if (q.empty()) {
            is_cycle = true;
            break;
        }
        // 한번에 두 정점 이상 큐에 들어갔다는 것은 순서가 불확실하다는 의미
        else if (q.size() >= 2) {
            is_certain = false;
            break;
        }
        int cur = q.front();
        q.pop();
        result.push_back(cur);

        for (int j = 1; j <= n; j++) {
            if (adj[cur][j]) {
                in_degree[j]--;
                if (in_degree[j] == 0)
                    q.push(j);
            }
        }
    }
    if (is_cycle)
        cout << "IMPOSSIBLE\n";
    else if (!is_certain)
        cout << "?\n";
    else {
        for (int i = 0; i < n; i++)
            cout << result[i] << ' ';
        cout << '\n';
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        ranking = vector<int>(n + 1);
        in_degree = vector<int>(n + 1, 0);
        adj = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));
        for (int i = 1; i <= n; i++)
            cin >> ranking[i];

        // 순위를 기준으로 인접 배열을 만들어준다
        for (int i = 1; i < n; i++)
            for (int j = i + 1; j <= n; j++) {
                adj[ranking[i]][ranking[j]] = true;
                in_degree[ranking[j]]++;
            }

        cin >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            if (adj[a][b]) {
                adj[a][b] = false;
                adj[b][a] = true;
                in_degree[a]++;
                in_degree[b]--;
            }
            else {
                adj[a][b] = true;
                adj[b][a] = false;
                in_degree[a]--;
                in_degree[b]++;
            }
        }
        topological_sort();
    }
    return 0;
}

Python3

import sys
from collections import deque


def topological_sort():
    result = []
    q = deque()

    for i in range(1, n + 1):
        if in_degree[i] == 0:
            q.append(i)

    is_cycle = False
    is_certain = True

    # 위상 정렬을 정점의 개수만큼 반복한다
    # (한번에 한 정점만 큐에 들어가야지 확실한 등수가 나오기 때문에)
    for i in range(n):
        # 반복문이 끝나기 전에 큐가 비었다는 것은 사이클이라는 의미
        if len(q) == 0:
            is_cycle = True
            break
        # 한번에 두 정점 이상 큐에 들어갔다는 것은 순서가 불확실하다는 의미
        elif len(q) >= 2:
            is_certain = False
            break
        cur = q.popleft()
        result.append(cur)

        for j in range(1, n + 1):
            if adj[cur][j]:
                in_degree[j] -= 1
                if in_degree[j] == 0:
                    q.append(j)
    if is_cycle:
        print("IMPOSSIBLE")
    elif not is_certain:
        print("?")
    else:
        for i in result:
            print(i, end=' ')
        print()


t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    in_degree = [0 for _ in range(n + 1)]
    adj = [[False] * (n + 1) for _ in range(n + 1)]
    ranking = list(map(int, sys.stdin.readline().rstrip().split()))

    # 순위를 기준으로 인접 배열을 만들어준다
    for i in range(n - 1):
        for j in range(i + 1, n):
            adj[ranking[i]][ranking[j]] = True
            in_degree[ranking[j]] += 1
    m = int(sys.stdin.readline().rstrip())
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        if adj[a][b]:
            adj[a][b] = False
            adj[b][a] = True
            in_degree[a] += 1
            in_degree[b] -= 1
        else:
            adj[a][b] = True
            adj[b][a] = False
            in_degree[a] -= 1
            in_degree[b] += 1
    topological_sort()