[C++]백준 - 3665번 문제

3665번: 최종 순위 (acmicpc.net)

3665번: 최종 순위

 

3665번 : 최종 순위

---

올해 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"을 출력한다.

---

 

생각해 볼 점

---

위상 정렬 문제입니다.

 

입력을 받고, 위상에 따른 그래프를 작성합니다.

 

 

화살표가 나타내는 것은 A -> B일 경우

 

A보다 B가 순위가 낮다는 뜻입니다.

(P.S : 저 같은 경우, 순위가 높은 쪽으로 구현했으나 어느쪽이든 상관없습니다.) 

 

지금은 5가 1등이니, 다른 나머지 팀들은 순위가 5보다 낮으므로 모두에게 연결해줍니다.

 

 

이런식으로 위상정렬을 위한 그래프를 작성하였다면,

 

다음은 순위를 변경해줍니다.

 

예시 입력에는 2와 4, 3과 4의 순위가 바뀌고 있습니다.

 

그러면, 해당 화살표만 반대로 뒤집어줍니다.

 

 

 

그 후, 위상 정렬 알고리즘을 실행합니다.

 

들어오는 화살표가 1개도 없는 노드를 골라서, 노드와 모든 에지를 제거합니다.

 

제거된 노드는 정답 배열에 추가합니다.

 

이제, 다음으로 들어오는 화살표가 하나도 없는 2를 택해서 제거합니다.

 

 

이제 4를 제거하고, 3을 제거하고, 1을 제거하면 정답이 나옵니다.

 

답 : 5 -> 2- -> 4 -> 3 -> 1

 

 

만약, 들어오는 화살표가 1개도 없는 노드가 여러개일 경우, 확실한 순위를 매길 수 없으니

 

"?"을 출력합니다.

 

만약, 모든 노드가 들어오는 화살표를 갖고 있어서 더 이상 진행이 안되는 경우에는

 

본부에서 이상한 정보를 준 것이므로 "IMPOSSIBLE"을 출력합니다.

 

코드

---

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

vector<int>* edges;


int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int N;
		scanf("%d", &N);

		edges = new vector<int>[N];
		int* in_count = new int[N];	//들어오는 에지의 수
		fill_n(in_count, N, 0);

		int a;
		scanf("%d", &a);
		a--;

		int first = a;
		for (int i = 1; i < N; i++)
		{	
			int b;
			scanf("%d", &b);
			b--;
			edges[b].push_back(a);
			in_count[a]++;
			for (int edge : edges[a])
			{
				edges[b].push_back(edge);
				in_count[edge]++;
			}
			a = b;
		}
		int M;
		scanf("%d", &M);

		//위상 변경
		for (int i = 0; i < M; i++)
		{
			int b;
			scanf("%d %d", &a, &b);
			a--; b--;
			auto it = find(edges[a].begin(), edges[a].end(), b);
			if (it != edges[a].end())
			{
				edges[a].erase(it);
				edges[b].push_back(a);
				in_count[b]--;
				in_count[a]++;
			}
			else
			{
				it = find(edges[b].begin(), edges[b].end(), a);
				edges[b].erase(it);
				edges[a].push_back(b);
				in_count[b]++;
				in_count[a]--;
			}
		}

		//위상정렬 알고리즘
		stack<int> ans;
		bool possible = true;
		for (int i = 0; i < N; i++)
		{
			int next;
			int count = 0;
			for (int j = 0; j < N; j++)
			{
				if (in_count[j] == 0)
				{
					count++;
					next = j;
					in_count[j] = -1;
					ans.push(j + 1);					
				}
			}

			//다음 에지가 없어서 불가능
			if (count == 0)
			{
				possible = false;
				printf("IMPOSSIBLE");
				break;
			}
			//모호함
			if (1 < count)
			{
				possible = false;
				printf("?");
				break;
			}
			for (int edge : edges[next]) in_count[edge]--;
		}

		if (possible)
		{
			while (!ans.empty())
			{
				printf("%d ", ans.top());
				ans.pop();
			}
		}
		printf("\n");

		delete[] edges;
		delete[] in_count;
	}
	return 0;
}

 

그 외

---