문제
https://www.acmicpc.net/problem/3665
풀이
올해 N개의 팀의 순위를 정할 때 위상 정렬을 이용할 수 있다.
위상 정렬은 사이클이 없는 방향 그래프에서 각 노드를 방향성에 거스르지 않도록 순서대로 나열할 때 사용하는 알고리즘이기 때문이다.
단, 이 문제에서는 작년의 순위와 등수 변경 데이터를 기준으로 새로운 그래프를 만든 이후 위상 정렬을 수행해야 한다.
이때 진입차수가 0인 노드가 2개 이상이면, 올해의 순위를 딱 하나로 정할 수 없으므로 "?"를 출력한다.
그리고 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있으며, 이 경우에는 올해 순위를 정할 수 없으므로 "IMPOSSIBLE"을 출력한다.
사이클에 포함된 모든 노드들은 진입차수가 1 이상이어서 큐에 들어가지 못하기 때문이다.
위의 두 가지 경우가 아니면 정상적으로 올해 순위를 결정해서 출력하면 된다.
그리고 중요한 점은 그래프의 구성 방법인데
1위 : -
2위 : 1위
3위 : 1위, 2위
4위 : 1위, 2위, 3위
...
N위 : 1위, 2위, ..., (N-1)위
이렇게 본인보다 순위가 높은 팀의 번호를 인접 행렬에 저장해주면 된다.
인접 리스트를 이용하면 두 팀의 순위를 바꾸기 위해 원소를 추가 / 삭제해야 하는데
인접 행렬을 이용하면 graph[a][b] = 1 → graph[b][a] = 1
이런 식으로 배열 원소의 값만 바꿔주면 되기 때문에 더 편리하다.
최종적으로 사이클이 없는 방향 그래프의 간선이 a → b → c → d → e 라고 하면
뒤쪽으로 갈수록 순위가 높은 것이기 때문에
정답을 출력할 때는 e, d, c, b, a 처럼 순서를 뒤집어서 출력해줘야 한다.
그리고 각 테스트 케이스마다 배열이나 변수의 데이터를 초기화 시켜줘야 한다는 걸 잊지말자!
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 501;
int T, N, M;
int rk[MAX]; // 작년 팀의 순위
int in[MAX]; // 각 팀의 진입차수
int graph[MAX][MAX]; // 인접 행렬
vector<int> ans; // 올해 팀의 순위
bool flag = false;
// 자신보다 높은 순위의 노드와 연결
void makeGraph(){
for(int i = 1; i <= N; i++){
for(int j = 1; j < i; j++){
graph[rk[i]][rk[j]] = 1;
in[rk[j]]++;
}
}
}
void swapRank(int a, int b){
// a -> b (a보다 b의 순위가 높은 경우)
if(graph[a][b] == 1){
// 간선 방향 뒤집기 b -> a
graph[a][b] = 0;
graph[b][a] = 1;
// 진입차수 갱신
in[b]--;
in[a]++;
}
// b -> a (b보다 a의 순위가 높은 경우)
else if(graph[b][a] == 1){
// a -> b
graph[b][a] = 0;
graph[a][b] = 1;
in[a]--;
in[b]++;
}
}
void printAnswer(){
for(int i = ans.size() - 1; i >= 0; i--){
cout << ans[i] << " ";
}
cout << "\n";
}
void initData(){
for(int i = 0; i <= N; i++){
for(int j = 0; j <= N; j++){
graph[i][j] = 0;
}
}
for(int i = 0; i <= N; i++){
rk[i] = 0;
in[i] = 0;
}
flag = false;
ans.clear();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while(T--){
cin >> N;
// 작년 팀의 순위 입력
for(int i = 1; i <= N; i++){
cin >> rk[i];
}
makeGraph();
cin >> M;
for(int i = 0; i < M; i++){
int a, b;
cin >> a >> b;
swapRank(a, b);
}
queue<int> q;
for(int i = 1; i <= N; i++){
if(in[i] == 0){
q.push(i);
}
}
while(!q.empty()){
// 진입차수가 0인 노드가 여러 개인지 검사
if(q.size() > 1) flag = true;
int now = q.front();
q.pop();
ans.push_back(now);
for(int i = 1; i <= N; i++){
if(graph[now][i] == 1){
in[i]--;
if(in[i] == 0){
q.push(i);
}
}
}
}
// 모든 노드를 처리하지 않았는데 큐가 비었다면 사이클 존재
if(ans.size() < N) cout << "IMPOSSIBLE\n";
else if(flag) cout << "?\n";
else{
printAnswer();
}
initData();
}
return 0;
}참고자료
