[백준] 3665번: 최종 순위

문제

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

설명

 위상 정렬 알고리즘을 사용해야 하며, 각 팀의 순위에 대한 선후 관계를 어떻게 관리할지, 상대적인 등수가 바뀐 팀들을 어떻게 처리할지, 확실한 순위를 찾을 수 없거나 순위를 하나로 정하지 못하는 경우는 어떤 경우인지 고려해야 한다.

 

 첫 번째 예제를 통해 살펴보자. 팀의 수 n은 5이고, 작년 팀의 순위는 5, 4, 3, 2, 1이다. 한 번 팀의 관계를 그래프로 나타내보자.

 

 위와 같이 팀의 관계를 그래프로 표현하였다. a->b는 a 팀이 b 팀보다 순위가 더 높다는 것을 의미한다. 첫 번째 예제에서 상대적인 등수가 바뀐 팀들은 (2, 4), (3, 4)이다. 먼저 단순히 두 팀의 위치 관계를 바꿔보는 것으로 생각해보자.

 

 2번 팀, 4번 팀의 위치를 바꾸었다. 이어서 3번 팀, 4번 팀의 위치를 바꾼다.

 

 결과는 5, 2, 4, 3, 1이지만, 첫 번째 예제의 정답은 5, 3, 2, 4, 1이다. 과연 어디서 잘못되었을까? 2번 팀과 4번 팀의 위치를 바꾼 상황으로 되돌아가보자.

 

 우리는 2번 팀, 4번 팀의 관계만 역전시켜야 한다. 그러나 2번 팀, 4번 팀의 위치를 단순히 바꾸게되면 3번 팀, 2번 팀의 관계 또한 바뀌게 된다. 즉, 각각의 팀은 본인을 제외한 다른 모든 팀과의 관계를 그래프로 유지해야 한다. 그래프로 표현하면 아래와 같다.

 

 조금 복잡하지만, 핵심은 팀의 모든 선후 관계를 나타냈다는 것이다. 이 상황에서 상대적인 순위가 바뀐 팀들을 서로 역전시키고, 위상 정렬을 수행하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;

		vector<int> last; // 작년 순위
		vector<int> inDegree(501);
		vector<int> lastRank(501); // lastRank[i] = x: i 팀의 작년 순위는 x
		vector<vector<int>> edge(501, vector<int>(501)); // edge[i][j] = 1: i -> j로의 간선이 존재함

		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x;
			last.push_back(x);
			lastRank[x] = i;
		}

		// 존재하는 모든 팀에 대해 가능한 간선을 설정한다. 즉, n(n+1)/2개의 간선을 생성한다.
		// a -> b: a가 순위 더 높음
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				int a = last[i];
				int b = last[j];

				inDegree[b]++;
				edge[a][b] = 1;
			}
		}

		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;

			// 둘의 관계를 뒤집는다.
			if (lastRank[a] < lastRank[b]) {
				inDegree[b]--;
				inDegree[a]++;
				edge[a][b] = 0;
				edge[b][a] = 1;
			}
			else {
				inDegree[a]--;
				inDegree[b]++;
				edge[a][b] = 1;
				edge[b][a] = 0;
			}
		}

		queue<int> q;
		for (int i = 1; i <= n; i++) {
			if (!inDegree[i]) {
				q.push(i);
			}
		}

		vector<int> ans;
		bool impossible = true;
		bool notUniqueAnswer = false;
		while (!q.empty()) {
			// inDegree가 0인 노드가 두 개 이상이면 순서를 하나로 정할 수 없음
			if (q.size() >= 2) {
				notUniqueAnswer = true;
				break;
			}

			int x = q.front();
			q.pop();
			ans.push_back(x);


			for (int i = 1; i <= n; i++) {
				if (edge[x][i]) {
					int y = i;
					inDegree[y]--;

					if (!inDegree[y]) {
						impossible = false;
						q.push(y);
					}
				}
			}
		}

		// 모든 노드를 방문하지 못한 경우 순서를 정할 수 없음
		if (ans.size() != n) {
			impossible = true;
		}

		if (impossible)
			cout << "IMPOSSIBLE";
		else if (notUniqueAnswer)
			cout << "?";
		else {
			for (int i = 0; i < n; i++) {
				cout << ans[i] << " ";
			}
		}
		cout << "\n";
	}
}