백준 3665 최종 순위 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/3665

문제 추상화

• 기존의 순서가 주어지고
• 바뀌어야할 순서 주어질떄
• 새로운 순서 구하기

아이디어

• topological sort 사용

  • https://dev-jango.tistory.com/12?category=961720
    • 기존 순위 따라가면서 adj 만든 후

• 바뀐 순서 따라가면서 adj에 추가

• 그럼 기존에 만들었던 adj는 어떻게하지?

  • 인접한건 뺼수 있는데
  • 인접하지 않은건?

• adj추가할때 후순위를 모두 넣으면 가능?

  • 그럼 인접하지 않은것도 확인가능

• 순위를 찾을수 없는 경우 : 큐에 한번에 두개 이상이 들어올떄

• 데이터 일관성 없어서 순위 못정하는 경우 : 전체 사이즈가 N이 안될때

  
  

시간복잡도 계산

• 테스트케이스 O(T)
• 각 노드에서 adj, indeg 생성(O(N^2))
• 바뀐쌍마다 adj수정 : O(M * N)
• topo 수행 : O(V+E) : O(N^2)
• 총합 : O(T * (N^2 + MN + N^2)) = O(T*MN) = 1e9 (약간 불안)

인트 계산

• indeg밖에없는데, 최대 N 가능

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool chk[510];
vector<int> adj[510];
int indeg[510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(chk, chk+510, 0);
        fill(indeg, indeg+510, 0);
        for(int i=0; i<510; i++) adj[i].clear();
        
        int N; cin >> N;
        for(int i=0; i<N; i++) {
            int e; cin >> e;
            chk[e]=1;
            for(int j=1; j<=N; j++) {
                if(chk[j] == false) {
                    adj[e].push_back(j);
                    indeg[j]++;
                }
            }
        }
        
        int M; cin >> M;
        for(int i=0; i<M; i++) {
            int a,b; cin >> a >> b;
            vector<int>::iterator it = find(adj[b].begin(), adj[b].end(), a);
            if(it != adj[b].end()) {
                adj[b].erase(it);
                indeg[a]--;
                adj[a].push_back(b);
                indeg[b]++;
            } else {
                it = find(adj[a].begin(), adj[a].end(), b);
                adj[a].erase(it);
                indeg[b]--;
                adj[b].push_back(a);
                indeg[a]++;
            }
        }
        
        vector<int> rs;
        queue<int> q;
        for(int i=1; i<=N; i++) {
            if(indeg[i] == 0) q.push(i);
        }
        
        // 확실한 순위를 찾을수 없을때가 언제지?
        // 서로 순서가 꼬이면
        // 예를들면 1,2,3 인데 1,3만 바뀌면 2,3 관계가 순서가 꼬임
        // 순서가 꼬이는경우 > 큐에 여러개 들어갈때
        bool sw = false;
        while(!q.empty()) {
            if(q.size() >1) {
                sw= true;
                break;
            }
            int eq = q.front(); q.pop();
            rs.push_back(eq);
            
            for(int x : adj[eq]) {
                indeg[x]--;
                if(indeg[x] == 0) q.push(x);
            }
            
        }
        if(sw == true) cout << '?' << '\n';
        else if(rs.size() != N) cout << "IMPOSSIBLE" << '\n';
        else {
            for(int x : rs) cout << x << ' ';
            cout << '\n';
        }
        
    }
    return 0;
}
 

문제유형

• 순위를 찾을 수 없는 경우
  • 큐에 한번에 여러개의 노드가 들어갈때
• 일관성 없는 경우
  • 사이클이 발생한 것
  • 결과의 사이즈가 노드 개수랑 다를때