BOJ 3665 최종 순위 [C++]

위상정렬 문제이다.

하지만 문제에서 주어진 입력에서 각 팀 사이의 관계를 추출하는 것이 어려웠다.

 

#include <bits/stdc++.h>

using namespace std;

int main() {

	int tt; cin >> tt;

	for (int ttt = 0; ttt < tt; ttt++) {
		int n, buf1,buf2, m;
		cin >> n;
		vector<bool> same(n + 1,true);
		vector<int> next[501], pre(n + 1), temp;
		map<int, int> rank,high,low;

		for (int i = 0; i < n; i++) {
			cin >> buf1; temp.push_back(buf1);
			rank[buf1] = i + 1;
			low[buf1] = i + 1;
			high[buf1] = i + 1;
		}
		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> buf1 >> buf2;
			same[buf1] = false;
			same[buf2] = false;
			if (rank[buf1] > rank[buf2]) {//이젠 buf2가 덜 우수
				high[buf1] = rank[buf2]; high[buf2] = rank[buf2];
				low[buf1] = rank[buf1]; low[buf2] = rank[buf1];
			}
			else {
				high[buf1] = rank[buf1]; high[buf2] = rank[buf1];
				low[buf1] = rank[buf2]; low[buf2] = rank[buf2];
			}

		}


		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {
				if (high[j] > low[i]) {
					next[i].push_back(j);
					pre[j]++;
				}
			}
			
		}


		for (int i = 1; i <= n; i++) {
			printf("%d : pre=%d   ", i,pre[i]);
			for (int j = 0; j < next[i].size(); j++) {
				cout << next[i][j] << " ";
			}
			cout << endl;
		}

		queue<int> q;
		vector<int> result;
		for (int i = 1; i <= n; i++)
			if (pre[i] == 0)
				q.push(i);

		while (!q.empty()) {
			int now = q.front();
			result.push_back(now);
			q.pop();

			for (int i = 0; i < next[now].size(); i++) {
				int ne = next[now][i];
				pre[ne]--;
				if (pre[ne] == 0) q.push(ne);
			}
		}

		int ok = true;
		for(int i=1;i<=n;i++)
			if (pre[i] != 0) {
				ok = false;
				break;
			}

		if (ok) {
			for (int i = 0; i < n; i++) {
				cout << result[i] << " ";
			}
			cout << "\n";
		}
		else {
			cout << "IMPOSSIBLE\n";
		}
		

	}

	return 0;
}

이 위의 코드는 가장 먼저 시도해본 방법이다. 위에서는 각 팀별 가능한 최고 순위와 가능한 최저 순위를 딕셔너리를 이용해 저장해두었다. 그리고 순위 역전이 있는 팀에 대해 최고순위와 최저순위를 처리해주었다.

마지막으로 전체 팀에 대하여 A팀의 가능한 최저 순위보다 B팀의 가능한 최고 순위가 낮다면, B팀은 A팀보다 아래다! 라는 의미로 받아들였다. 또한 순위의 변동이 없는 것들을 same벡터에 담았다. 하지만 첫번째 예제 입출력부터 문제가 생긴다.

 

1
5
5 4 3 2 1
2
2 4
3 4

이 테스트케이스에 대해 백준에서 제시된 정답은 5 3 2 4 1이지만,

위 코드는 5 2 3 4 1이라 출력한다. 입력의 의미를 잘 따져보면 3과 2사이에는 역전이 없다. 하지만 내 코드에서는 2가 3보다 뒤라는 것을 처리해주지 못한다. 둘다 high, low를 이용해 비교하기 때문이다.

 

따라서 입력에서 순위를 추출할 다른 방법을 찾아보았다.

 

아래가 AC받은 코드이다.

#include <bits/stdc++.h>

using namespace std;

int main() {

	int tt; cin >> tt;

	for (int ttt = 0; ttt < tt; ttt++) {
		int n, buf1,buf2, m;
		cin >> n;
		vector<int> temp(n);
		vector<bool> same(n + 1,true);
		vector<vector<bool>> adj(n + 1, vector<bool>(n + 1));

		for (int i = 0; i < n; i++)
			cin >> temp[i];

		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
				adj[temp[i]][temp[j]] = true;
		

		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> buf1 >> buf2;
			adj[buf1][buf2] = !adj[buf1][buf2];
			adj[buf2][buf1] = !adj[buf2][buf1];
		}

		vector<int> next[501], pre(n + 1, 0);

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (adj[i][j]) {
					next[i].push_back(j);
					pre[j]++;
				}
			}
		}

		/*for (int i = 1; i <= n; i++) {
			printf("%d : pre=%d   ", i, pre[i]);
			for (int j = 0; j < next[i].size(); j++) {
				cout << next[i][j] << " ";
			}
			cout << endl;
		}*/
		

		queue<int> q;
		vector<int> result;
		for (int i = 1; i <= n; i++)
			if (pre[i] == 0)
				q.push(i);

		while (!q.empty()) {
			int now = q.front();
			result.push_back(now);
			q.pop();

			for (int i = 0; i < next[now].size(); i++) {
				int ne = next[now][i];
				pre[ne]--;
				if (pre[ne] == 0) q.push(ne);
			}
		}

		int ok = true;
		for(int i=1;i<=n;i++)
			if (pre[i] != 0) {
				ok = false;
				break;
			}

		if (ok) {
			for (int i = 0; i < n; i++) {
				cout << result[i] << " ";
			}
			cout << "\n";
		}
		else {
			cout << "IMPOSSIBLE\n";
		}
		

	}

	return 0;
}

 

그 방법은 먼저 작년도 순위를 입력받는다. 그리고 작년도에 A팀보다 B팀이 낮았다면 그러한 가능한 B팀 모두를 A팀보다 아래다! 라고 알려줘야한다. 이때는 boolean형 인접행렬(adj)을 사용해였다.

다음으로 순위가 역전되는 팀에 대해서는 adj[A][B]를 반대 논리값으로, adj[B][A]를 반대 논리값으로 바꾸었다.

이 뜻은 만약 작년에 A보다 B가 뒤였다면(adj[A][B]==true) 이제는 B보다 A가 뒤(adj[B][A]==true)이고,

A보다 B가 뒤가 아니다(adj[A][B]==false)라는 뜻이다. 아까는 랭크를 map에 저장하고, 비교하고 바꾸었는데 이것이 훨씬 간결하다.

 

마지막으로 모든 팀과 팀 사이에서 선후 관계를 입력받아서 next배열에 넣고, 선행자가 몇개인지 ++시켜준다.

(주석처리된 코드는 디버깅용으로 각 팀 앞에는 몇개의 팀이 있고, 뒤에는 어떤 팀들이 있는지 출력하는 코드이다.)

 

마지막으로 위상정렬 알고리즘에 넣어주면 끝.이긴 한데, 문제의 출력조건을 잘 보면 확실한 순위를 찾을 수 없다면 "?"를 출력하라고 되어있다. 다시말해, 가능한 순위가 여러개인 경우에는 "?"를 출력하라는 것이다. 하지만 실제로 ?가 출력되는 경우는 존재하지 않는다. 왜 그럴까?

boj 3665번 질문 게시판을 참고하면 일관성이 없다는 것을 사이클이 생긴다는 것이다.

가능한 순위인 답이 여러개 나온다는 것은 상대적인 순위 변경에 대한 정보가 부족하다는 것이다.

하지만 문제 지문 3문단에서는 상대적인 순위가 바뀐 모든 팀의 목록이 주어진다고 한다.

이 목록 전체를 이용하면 시간은 오래걸리겠지만 완전 탐색을 통해 유일한 해를 얻을 수 있다.

(이 증명이 썩 내키진 않는다. 더 확실한 증명을 생각해봐야겠다.)

 

따라서 정보가 부족해 여러가지 답이 나오는 경우는 존재하지 않는다는 것이다.

따라서 "?"인 경우는 존재하지 않는다.