[백준/BOJ] 백준 3665번 : 최종 순위

www.acmicpc.net/problem/3665

3665번: 최종 순위

위상 정렬을 이용하였다. 그래프를 연결할 때 우선 작년 순위 기준으로 뒷순위로 가는 모든 연결을 하였다. 그리고 상대적인 순위가 바뀐 팀의 목록이 주어질 때 그 팀들의 연결을 수정하였다. 중간에 큐의 크기가 1이 아니라면 확실한 순위를 찾을 수 없다고 판단하고, 최종 결과 순위 목록의 크기가 n이 아니라면 순위를 정할 수 없다고 판단하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int tc;
vector<int> adj[501];
vector<int>::iterator it;
vector<int> indegree(501);
vector<int> number_to_rank(501); //i팀이 작년에 몇등을 했는지 저장

void Pre()
{
	for (int i = 0; i < 501; i++)
	{
		adj[i].clear();
		indegree[i] = 0;
		number_to_rank[i] = 0;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();
		string check = " ";

		int n;
		cin >> n;

		vector<int> last_year;
		for (int i = 0; i < n; i++)
		{
			int t;
			cin >> t;

			last_year.push_back(t);
		}

		for (int i = 0; i < last_year.size(); i++)
		{
			number_to_rank[last_year[i]] = i + 1;

			if (i != last_year.size() - 1)
			{
				//위상정렬을 위한 그래프 만들기
				for (int j = i + 1; j < last_year.size(); j++)
				{
					adj[last_year[i]].push_back(last_year[j]);

					indegree[last_year[j]]++;
				}
			}
		}

		int m;
		cin >> m;

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

			//그래프의 연결을 수정
			if (number_to_rank[a] < number_to_rank[b])
			{
				it = find(adj[a].begin(), adj[a].end(), b);

				adj[a].erase(it);
				indegree[b]--;

				adj[b].push_back(a);
				indegree[a]++;
			}
			else
			{
				it = find(adj[b].begin(), adj[b].end(), a);

				adj[b].erase(it);
				indegree[a]--;

				adj[a].push_back(b);
				indegree[b]++;
			}
		}

		queue<int> q;
		vector<int> result;

		for (int i = 1; i <= n; i++)
		{
			if (indegree[i] == 0)
				q.push(i);
		}

		while (!q.empty())
		{
			if (q.size() != 1) //확실한 순위를 찾을 수 없을때
				check = "?";

			int here = q.front();
			q.pop();

			result.push_back(here);

			for (int i = 0; i < adj[here].size(); i++)
			{
				int there = adj[here][i];

				indegree[there]--;

				if (indegree[there] == 0)
					q.push(there);
			}
		}

		if (result.size() != n) //순위를 정할 수 없을때
			check = "IMPOSSIBLE";

		if (check != " ")
			cout << check << "\n";

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

	return 0;
}