[C++] 3665번 최종 순위 - 그래프 이론, 위상 정렬

1. 문제

• n개의 팀은 1~n번까지 번호가 매겨져 있고 작년과 참가한 팀이 같다. 작년 순위와 상대적인 순위가 바뀐 모든 팀이 주어졌을 때, 올해 순위를 만드시오. 하지만 올해 순위가 결정되지 않을 수도 있고, 잘못된 정보일 수도 있어 이도 알아내야 한다.

<입력>

• - 1 -   테스트 케이스의 개수 \(T(1 \leq T \leq 100)\)
  • - 1 -   팀의 수 \(n(2 \leq n \leq 500)\)
  • - 2 -   \(t_{i}(1 \leq t_{i} \leq n)\). \(t_{i}\)는 작년에 i 등 한 팀의 번호
  • - 3 -   상대적인 등수가 바뀐 쌍의 수 \(m(0 \leq m \leq 25,000)\)
  • - m개의 줄 -   상대적인 등수가 바뀐 두 팀. 중복은 X

<출력>

• 1등팀부터 순위 출력. 순위가 결정되지 않을 경우?, 순위를 정할 수 없는 경우 IMPOSSIBIL을 출력.

2. 재정의

• 전 순서와 바뀐 순서가 주어졌을 때, 현 순서를 정하기

3. 해결 방법

• 모든 팀의 순위를 파악하기
• (a, b)인 경우 a가 b보다 순위가 낮았으면 a->b, 그렇지 않으면 b->a가 되도록 하고 낮은 순위는 모두 높은 순위와 연결시켜주기
• 사이클이 발생하면 impossible을, q.size()>2이면 ?을 출력하기

4. 실수한 점, 개선할 점

• (a, b)의 의미는 a가 b보다 순위가 높다는 것이 아닌, a와 b의 상대적인 순위가 바뀌었다는 의미이다.
• 순서가 바뀐 모든 경우가 주어지므로 ?가 출력될 일은 없다.

 

<코드>

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

const int MAX_N = 501;

// <문제>
// 테스트 케이스의 개수 T
int T;
// 팀의 수 N, 상대적인 등수가 바뀐 팀의 쌍 수 M
int N, M;
// 팀의 순위 t[], tRank[]
int t[MAX_N], tRank[MAX_N];
// 팀의 상대적인 순위 순서 adj
vector<int> adj[MAX_N];
// 바뀐 팀의 상대 순서 revadj
bool revadj[MAX_N][MAX_N];

// topology Sort
// 진입차수가 0인 노드 보관하는 queue
queue<int> q;
// 진입차수 inDegree[]
int inDegree[MAX_N];
// 위상정렬 결과 result[]
int result[MAX_N];

void input() {
    // 자료 초기화
    while(!q.empty())
        q.pop();
    memset(inDegree, 0, sizeof inDegree);
    memset(result, 0, sizeof result);
    memset(t, 0, sizeof t);
    memset(tRank, 0, sizeof tRank);
    for(int i=0; i<MAX_N; i++)
        adj[i].clear();
    memset(revadj, false, sizeof revadj);
    
    cin >> N;
    int Rank = 1;
    for(int i=0; i<N; i++) {
        cin >> t[i];
        tRank[t[i]] = Rank++;
    }
    
    cin >> M;
    // 작년과 달라진 상대 순서
    for(int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        if(tRank[a] > tRank[b])
            revadj[a][b] = true;
        else
            revadj[b][a] = true;
    }
    
    // 위상정렬 용 순서 단방향 그래프 만들기
    for(int i=N-1; i>=0; i--) {
        int a = t[i];
        for(int j=i-1; j>=0; j--) {
            int b = t[j];
            
            // 작년과 상대 순서가 달라졌으면 반대로 추가
            if(revadj[a][b]) {
                adj[b].push_back(a);
                inDegree[a]++;
            }
            else {
                adj[a].push_back(b);
                inDegree[b]++;
            }
        }
    }
}

// 위상정렬
/*
    2: 위상정렬 잘됨
    1: 가능한 경우가 여러가지 (queue.size()>1)
    0: 사이클이 발생
*/
bool topologySort() {
    for(int i=1; i<=N; i++) {
        if(!inDegree[i])
            q.push(i);
    }
    
    for(int i=0; i<N; i++) {
        // 큐가 비었다는 것은 사이클이 발생한 것
        if(!q.size())
            return false;
        
        int x = q.front(); 
        q.pop();
        result[i] = x;
        for(auto next : adj[x]) {
            if(!(--inDegree[next]))
                q.push(next);
        }
    }
    
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--) {
        input();
        
        bool flag = topologySort();
        
        if(flag) {
            for(int i=N-1; i>=0; i--)
                cout << result[i] << ' ';
        }
        else
            cout << "IMPOSSIBLE";
        cout << '\n';
    }
}

<C++ queue>

https://life-with-coding.tistory.com/408

[C++][STL] Queue 기본 사용법 및 예제

 

<문제 바로가기>

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

3665번: 최종 순위

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.