문제
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.
올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.
창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.
입력
첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
- 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
- n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다.
- 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
- 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.
출력
각 테스트 케이스에 대해서 다음을 출력한다.
- n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
풀이
작년도 순위(pre_ranking)을 입력받는다.
작년 순위에서 한 팀에대해 그 팀보다 낮은 순위를 기록한 모든 팀에게 간선을 내린다.
- 1위팀은 n-1개의 간선을 가진다.
- 꼴등팀은 0개의 간선을 가지며 n-1개의
indegree를 가진다
올해의 상대적인 순위 변동을 반영하기 위해서는 최대한 많은 간선을 이용하여 표현해야 한다고 생각했다.
또한 순위 변동을 처리하기 위해서는 특정 간선을 찾아 제거하거나 새로 만드는 작업이 필요한데, 이를 상수시간에 해결하기 위해 인접행렬로 표현하였다. 간선의 수도 많아 인접행렬로 표현했을 때의 단점이 크지 않다.
순위 변동이 있는 팀 두갤르 입력 받으면 그 두 팀의 간선의 방향을 바꾼다.
인접행렬로 표현하였으므로 빠르고 간단하게 변경이 가능하다.
indegree도 알맞게 변경해준다.
올해의 상대 순위 변경이 끝났다면 위상정렬로 모든 모드를 탐색해본다.
탐색된 노드들을 순서대로 new_ranking에 저장한 후 출력한다.
만약 데이터의 일관성이 없어 그래프에서 사이클이 발생한다면 교착상태가 되어 탐색하지 못한 노드가 생긴다.
이는 노드의 indegree 값을 검사하여 0보다 크다면 탐색되지 못한 노드이다.
이때에는 "IMPOSSIBLE"을 출력한다.
확실한 순위를 찾을 수 없는 경우는 발생하지 않는다.
사이클이 발생하지 않고 순위를 찾을 수 없는 경우는 간선이 사라져야 발생하지만, 문제에서는 간선을 변경하는 경우는 있어도 삭제하는 경우는 없기 때문이다.
코드
#include <iostream>
#include <vector>
using namespace std;
int T, n, m;
vector<vector<bool>> edges;
vector<int> indegree;
vector<int> pre_ranking;
vector<int> new_ranking;
// 간선의 방향과 indegree값을 변경한다
void swapEdge(int a, int b){
if ((edges[a][b] = !edges[a][b])){
indegree[a]--;
indegree[b]++;
}
if ((edges[b][a] = !edges[b][a])){
indegree[a]++;
indegree[b]--;
}
// int winner, loser;
// if (edges[a][b]){
// winner = a;
// loser = b;
// }
// else{
// winner = b;
// loser = a;
// }
// edges[winner][loser] = false;
// edges[loser][winner] = true;
// indegree[winner]++;
// indegree[loser]--;
}
void dfs(int v, vector<int>& new_ranking){
new_ranking.push_back(v);
for (int i=1; i < n+1; i++){
if (!edges[v][i]) continue;
if (--indegree[i] == 0) dfs(i, new_ranking);
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> T;
while (T--){
cin >> n;
// 초기화
edges.assign(n+1, vector<bool>(n+1, false));
indegree.assign(n+1, 0);
pre_ranking.clear();
new_ranking.clear();
for (int i=0; i < n; i++){
int input;
cin >> input;
pre_ranking.push_back(input);
}
// 간선 생성: 자신보다 낮은 모든 팀에 간선 생성, 꼴등 팀은 indegree가 가장 높다.
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
int winner = pre_ranking[i];
int loser = pre_ranking[j];
edges[winner][loser] = true;
indegree[loser]++;
}
}
cin >> m;
for (int i=0; i<m; i++){
int a, b;
cin >> a >> b;
swapEdge(a, b);
}
// 위상정렬 순회
for (int i=1; i<n+1; i++){
if (indegree[i] == 0){
dfs(i, new_ranking);
break; // 이걸 안했더니 dfs 한번 쭉 돌고 나서 for 문이 돌게 될때 그때 indegree가 0인 놈을 호출해버림
}
}
// 사이클 검사 (데이터의 일관성 검사)
bool isCycle = false;
for (int i=1; i<n+1; i++){
// dfs 를 돌고 난 뒤에 indegree의 값이 0 이상인 노드가 있다면 사이클이 발생해서 모든 노드를 순회하지 못한 것이다.
if (indegree[i] > 0) {
isCycle = true;
}
}
if (isCycle) {
cout << "IMPOSSIBLE";
}
else {
for (auto i: new_ranking)
cout << i << " ";
}
cout << "\n";
}
return 0;
}