백준 3665번 : 최종 순위 - 위상정렬 C++ 문제풀이 및 코드

https://www.acmicpc.net/problem/3665

3665번: 최종 순위

1. 문제설명

 

단방향 그래프 관계가 주어지고

 

그래프에서 간선의 방향을 수정했을 때

 

위상정렬을 수행하면 단 하나의 경우의 수만 나오는지 확인하는 문제다.

 

---

2. 접근방법[알고리즘]

 

우선 위상정렬을 수행하는데 확인해야 할 게 두가지 있다.

 

첫 번째는

단 하나의 경우의 수만 등장하는지 ==

확실한 순위를 찾을 수 있는지 확인해야한다.

이를 확인하려면 위상정렬을 하면서 큐의 size를 확인해야 한다.

만약 하나의 노드에서 여러 노드로 퍼질 수 있다면

큐의 사이즈가 2를 넘게 되고 이때는 위상정렬의 가짓 수가 여러개가 되어서 확실한 순위를 찾을 수 없다.

 

 

두번째는 

사이클이 존재하다면 IMPOSSIBLE을 출력해야한다.

사이클이 존재하면 위상정렬이 불가능하고,

그 경우에 위상정렬 과정에서 degree(차수) 가 0이 되지 않는 노드가 생기기 때문에

모든 노드를 탐색하지 못한다.

 

 

 

 

 

---

 

3. 문제풀이코드 C++

 

#include <bits/stdc++.h>
using namespace std;

bool adj[501][501];
int degree[501];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {

        memset(adj, 0, sizeof(adj));
        memset(degree, 0, sizeof(degree));
        int n;
        cin >> n;

        vector<int> pre;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            pre.push_back(tmp);
        }

		for (int i = 0; i < pre.size(); i++) {
            for (int j = i + 1; j < pre.size(); j++) {
                adj[pre[i]][pre[j]] = 1;
                degree[pre[j]]++;
            }
        }

        int m;
        cin >> m;


        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;

            if (adj[a][b] == 1) {
                adj[a][b] = 0;
                degree[b]--;
                adj[b][a] = 1;
                degree[a]++;
            }
            else {
                degree[a]--;
                adj[b][a] = 0;
                adj[a][b] = 1;
                degree[b]++;
            }
        }

        
        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
            }
        }

        vector<int> ans;

        bool cantKnow = false;

        while (!Q.empty()) {

            if (Q.size() >= 2) {
                cantKnow = true;
                break;
            }

            int x = Q.front(); Q.pop();
            ans.push_back(x);

            for (int i = 1; i <= n; i++) {
                if (adj[x][i] == 1) {
                    int nx = i;

                    if (--degree[nx] == 0) {
                        Q.push(nx);
                    }

                }
            }
        }

        if (cantKnow) {
            cout << "?\n";
            continue;
        }


        if (ans.size()!=n) {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        else {
			for (auto x : ans) {
				cout << x << ' ';
			}
			cout << '\n';
        }


    }
  
    return 0;
}

백준 3665번 : 최종 순위