백준 3665 최종 순위 혼내주기

 

adjacency matrix로 1 -> 2 -> 3 순서라면 아래와 같이 모든 순서를 표현한 뒤

 

1 -> 2
1 -> 3
2 -> 3

 

등수가 바뀐 순서만 적용해서 위상정렬을 하면 된다.

 

문제를 풀면서 아쉬웠던 점:
계산을 잘못해서 adj matrix로 바로 넘어가지 못함
아무리 생각해도 ?인 경우가 없는데, 문제에 써있다고 나를 의심함 => 낚임

 

이 문제를 풀면서 아직도 내가 키보드를 너무 일찍 잡는다는걸 느꼈다. 경우의 수와 complexity 계산을 정확히 하는 능력도 아직 부족하다...

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

bool adj[501][501];
int rnk[501], ind[501];
int t, n, m;

void input() {
    memset(adj, false, sizeof(adj));
    memset(ind, 0, sizeof(ind));

    int u; cin >> n;
    for(int i = 1; i <= n; ++i) 
        cin >> rnk[i];
    for(int i = 1; i <= n; ++i) {
        for(int j = i+1; j <= n; ++j) {
            adj[rnk[i]][rnk[j]] = true;
            ind[rnk[j]]++;
        }
    }
    cin >> m;
}

int main() {
    fastio;
    cin >> t;

    while(t--) {
        input();
        int u, v;
        for(int i = 1; i <= m; ++i) {
            cin >> u >> v;
            if(adj[u][v]) {
                adj[u][v] = false;
                adj[v][u] = true;
                ind[u]++;
                ind[v]--;
            }
            else {
                adj[v][u] = false;
                adj[u][v] = true;
                ind[v]++;
                ind[u]--;
            }
        }

        // find root
        int root;
        for(int i = 1; i <= n; ++i) {
            if(ind[i] == 0) {
                root = i;
                break;
            }
        }

        queue<int> order;
        queue<int> q;
        q.push(root);

        while(!q.empty()) {
            int from = q.front(); q.pop();
            order.push(from);
            for(int i = 1; i <= n; ++i) {
                if(adj[from][i]) {
                    if(--ind[i] == 0)
                        q.push(i);
                }
            }
        }

        if(order.size() == n) {
            while(!order.empty()) {
                cout << order.front() << " ";
                order.pop();
            }
            cout << "\n";
        } 
        else cout << "IMPOSSIBLE\n";
    }
}