알고리즘 :: 백준 :: 그래프 :: 3665 :: 최종 순위

문제

문제링크

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.
올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.
창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

문제접근

• 순위가 주어지므로 이 문제는 그래프(또는 트리)로 생각하면 위상정렬 문제임을 알 수 있다.
• 이 문제의 함정은 '작년 순위가 주어지기 때문에 ?는 나올 일이 없다는 것이다. 왜냐하면 입력으로 주어지지 않는 관계는 작년과 동일함을 의미하기 때문에 임의의 두 참가자 사이의 우열 관계는 반드시 파악 가능하다.
• 그러므로 이 문제에서는 논리 오류만 파악해서 IMPOSSIBLE만 잘 출력하면 되는 문제다.
  • 위상정렬을 사용한다는 점에서 우리는 이미 IMPOSSIBLE이 나타나는 경우: 시작 정점이 없는 경우 (indegree = 0인 점이 없는 경우)가 있음을 알고 있다.
  • 위상정렬 결과, 모든 정점을 표현하지 못했다면 IMPOSSIBLE을 출력해야함도 알고있다.
• 도구는 모두 주어졌으니 이제 indegree[] 배열을 잘 조작해서 순위를 바꾸는 연산만 잘 구현해보자.

코드

// https://www.acmicpc.net/problem/3665
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

static vector<int> indegree;
static vector<vector<int>> graph;

void topologySort(int size) {
    vector<int> answer;
    queue<int> q;
    for (int i = size; i > 0; --i)
        if (indegree[i] == 0) q.push(i);
    
    while (!q.empty()) {
        int curTeamNum = q.front(); q.pop();
        answer.push_back(curTeamNum);
        for (const int& next : graph[curTeamNum]) {
            indegree[next]--;
            if (indegree[next] == 0) q.push(next);
        }
    }
    if (answer.size() != size) { cout << "IMPOSSIBLE\n"; return; }

    for (const int& ele : answer) cout << ele << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int N;  cin >> N;
		// [과정1]:: 작년 순위를 입력받는다.
        vector<int> ranking(N);
        for (int i = 0; i < N; ++i) cin >> ranking[i];
        
		// [과정2]:: 매 loop마다 새로운 전역변수 공간 할당.
        graph = vector<vector<int>>(N + 1, vector<int>());
        indegree = vector<int>(N + 1);
	
		// [과정3]:: indegree 배열 초기화 및 그래프 간선 추가.
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                graph[ranking[i]].push_back(ranking[j]);
                indegree[ranking[j]]++;
            }
        }
		// [과정4]:: 바뀐 순위 적용
        int M;  cin >> M;
        for (int i = 0; i < M; ++i) {
            int team1, team2;   cin >> team1 >> team2;
			// 만일 team1 -> team2 순위가 바뀐다면 team2 -> team1로 바꿔주고 indegree 변경해준다.
            if (auto itr = find(begin(graph[team1]), end(graph[team1]), team2); itr != end(graph[team1])) {
                graph[team1].erase(itr);
                graph[team2].push_back(team1);
                indegree[team2]--;
                indegree[team1]++;
            }
			// 만일 team2 -> team1 순위가 바뀐다면 team1 -> team2로 바꿔주고 indegree 변경해준다.
            else if (auto itr = find(begin(graph[team2]), end(graph[team2]), team1); itr != end(graph[team2])) {
                graph[team2].erase(itr);
                graph[team1].push_back(team2);
                indegree[team1]--;
                indegree[team2]++;
            }
        }
		// [과정5]:: 위상정렬 실시
        topologySort(N);
    }
}

결과