백준 3665 최종 순위

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

3665번: 최종 순위

 

문제를 보자마자 위상 정렬 느낌이 난다.

 

특이한 점이 있다면, 두 팀의 상대순위를 바꾸는 작업을 할 때 다른 팀과의 상대 순위는 유지해야 한다는 점이다.

 

즉, 2->3->4 였는데 2와 4는 바꾼다고 해서 4->3->2를 하면 안된다!! 다른 곳은 단순히 Input을 받는 곳이고

 

solve() 함수에서 해결한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include<cstring>

#define MAX 500 + 1

using namespace std;

void init();
void input();
void solve();

int n_of_team, n_of_change;
bool win_loss_between_team[MAX][MAX];
int last_year_rank[MAX];
int num_of_in[MAX];
vector<int> answer;

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

	int t_case; cin >> t_case;
	for (int i = 0; i < t_case; i++) {
		init();
		input();
		solve();
	}

	return 0;
}

void init() {
	memset(win_loss_between_team, false, sizeof(win_loss_between_team));
	memset(last_year_rank, 0, sizeof(last_year_rank));
	memset(num_of_in, 0, sizeof(num_of_in));
	answer.clear();
}

void input() {
	cin >> n_of_team;
	for (int i = 1; i <= n_of_team; i++)
		cin >> last_year_rank[i];

	for (int i = 1; i <= n_of_team; i++) {
		for (int j = i + 1; j <= n_of_team; j++) {
			win_loss_between_team[last_year_rank[i]][last_year_rank[j]] = true;
			num_of_in[last_year_rank[j]]++;
		}
	}

	cin >> n_of_change;
	for (int i = 0; i < n_of_change; i++) {
		int a, b; cin >> a >> b;
		if (win_loss_between_team[a][b] == false)
			swap(a, b);

		win_loss_between_team[a][b] = false;
		win_loss_between_team[b][a] = true;

		num_of_in[b]--;
		num_of_in[a]++;
	}
}

void solve() {
	int root;
	bool exist = false;
	queue<int> q;
	for (int i = 1; i <= n_of_team; i++) {
		if (num_of_in[i] == 0) {
			root = i;
			exist = true;
		}
	}

	if (exist == false) {
		cout << "IMPOSSIBLE" << '\n';
		return;
	}

	q.push(root);

	int sizes = n_of_team ;
	while (sizes--) {
		if (q.empty()) {
			cout << "IMPOSSIBLE" << '\n';
			return;
		}

		int cur_node = q.front();
		answer.push_back(cur_node);
		q.pop();

		/* 큐가 비어있지 않다면 '꼭 이 노드로 위상정렬을 진행해야 할 이유가 없'으므로 
        문제에서 말한 '모호한 상태'가 된다. 그러니 ?를 출력하고 프로그램 종료 */
		if (!q.empty()) {
			cout << "?" << '\n';
			return;
		}

		/* 현재 노드에 비해 위상적으로 뒤에있는 노드의 in 값을 하나씩 줄인다.*/
		for (int i = 1; i <= n_of_team; i++) {
			if (win_loss_between_team[cur_node][i] == true) {
				num_of_in[i]--;

				if (num_of_in[i] == 0) { // 0이 되는 노드는 새로 넣는다. 
					q.push(i);
				}
			}
		}
	}	
	for (auto i : answer) {
		cout << i << " ";
	} cout << '\n';
}