[Graph] BOJ 3665 최종 순위

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

3665번: 최종 순위

순위의 개념을 그래프에 위상 정렬을 적용하여 나타낼 수 있는가를 묻는 문제이다.

다만 초반 그래프를 구성하는 것이 다소 까다롭다.

위상 정렬 (Topological Sort)

예제의 5, 4, 3, 2, 1을 통해 문제 해결법을 생각해보자.

 

순위를 그래프로 나타내려 했을 때, 일반적으로 떠오르는 그래프의 형태는 아래와 같을 것이다.

하지만 위 그래프는 문제의 순위 변동을 나타내기 힘들다.

문제에서 제시되는 순위의 변동은 "어떤 팀이 몇 등으로 올라갔다" 또는 "k번 팀과 l번 팀의 순위가 바뀌었다" 의 정보가 아닌, "작년엔 k번 팀이 l번 팀보다 앞순위였는데, 올해는 l번 팀이 k번 팀보다 앞순위다" 로 모호하기 때문이다.

즉, 한 팀의 변동 이후 순위를 확정지을 수 없기 때문에, 위의 직선형 그래프로는 이 문제를 해결하기 힘들다.

 

따라서, 위상 정렬을 적용하기 위해 그래프 내의 진입 차수(Indegree)를 조정하여 그래프를 다음과 같이 설정한다.

위 그래프에서 위상 정렬을 적용하면, 5, 4, 3, 2, 1 순서대로 큐에서 뽑혀 나온다. 이는 곧 각 정점의 진입 차수의 오름차순과도 같다.

따라서 순위 변동이 일어나면, 단지 변동이 일어난 두 정점의 간선 방향만 바꾸어주면 된다.

예제의 2, 4 변동이 일어났을 때 모습이다.

순위가 변동되어 2번 팀이 4번 팀보다 먼저 발견되어야 하므로, 두 정점 간의 간선 방향을 바꾼다.

이후 3, 4 변동이 일어나면, 그래프는 위와 같은 형태가 된다. 이 최종 그래프에서 위상 정렬을 적용하면 올해의 순위인 5, 3, 2, 4, 1을 얻을 수 있다.

 

※ 조건 : 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력

개념 포스팅에서 위상 정렬을 설명할 때, 위상 정렬을 적용할 수 없는 경우는 그래프에 사이클이 존재하는 경우라 했다.

즉, 위상 정렬을 적용하던 중 모든 정점을 방문하지 않고 큐가 비어 종료된 경우이다.

 

※ 조건 : 확실한 순위를 찾을 수 없다면 "?"를 출력

개념 포스팅에서 따로 언급하진 않았지만, 그래프에 따라 위상 정렬은 2개 이상의 결과를 낼 수 있다.

이는 2개 이상의 정점이 동시에 진입 차수가 0이 될 때 발생하며, 따라서 위상 정렬을 적용하던 도중 큐의 크기가 2 이상인 경우이다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
 
//team[i] = j 에서 기존 i등의 팀 번호가 j
//order[i] = j 에서 i번 팀의 기존 등수가 j
int n, m, team[501], order[501];        
int indegree[501];
bool adj[501][501];
vector<int> answer;
 
int topological_sort() {
    queue<int> que;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) que.push(i);
    }
 
    while (!que.empty()) {
        if (que.size() > 1) return 0;        //불확실한 순위
        int cur = que.front();
        que.pop();
 
        answer.push_back(team[cur]);
        if (answer.size() == n) return 1;        //올바른 순위
 
        for (int i = 1; i <= n; i++) {
            if (!adj[cur][i]) continue;
            adj[cur][i] = false;
            indegree[i]--;
            if (indegree[i] == 0) que.push(i);
        }
    }
    return -1;        //순위를 정할 수 없음
}
 
void init() {
    cin >> n;
 
    answer.clear();
    memset(team, 0, sizeof(team));
    memset(order, 0, sizeof(order));
    memset(adj, 0, sizeof(adj));
    memset(indegree, 0, sizeof(indegree));
 
    for (int i = 1; i <= n; i++) {
        cin >> team[i];
        order[team[i]] = i;
    }
 
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            adj[i][j] = true;
            indegree[j]++;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int tc, f, s;
    cin >> tc;
    for (int i = 0; i < tc; i++) {
        init();
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> f >> s;
            //f를 기존 앞순위, s를 기존 뒷순위로 둠
            if (order[f] > order[s]) swap(f, s);
            //뒷순위가 앞으로 오게 되었으므로, 두 팀의 간선을 뒤집는다.
            //원래는 f -> s로 가는 간선을 s -> f로 변환
            int node_f = order[f], node_s = order[s];
 
            adj[node_f][node_s] = false;
            indegree[node_s]--;
 
            adj[node_s][node_f] = true;
            indegree[node_f]++;
        }
        int result = topological_sort();
        if (result == -1) printf("IMPOSSIBLE\n");
        else if (result == 0) printf("?\n");
        else {
            for (int j = 0; j < answer.size(); j++) printf("%d ", answer[j]);
            printf("\n");
        }
    }
 
    return 0;
}