백준 3665 - 최종 순위(C++)

문제 링크입니다. https://www.acmicpc.net/problem/3665

3665번: 최종 순위

저번 순위가 주어지고 바뀐 상대적인 순위가 주어질 때, 올해의 최종 순위를 구하는 문제입니다.
최종 순위를 정확하게 구할 수 없다면 조건에 따라 ’?‘ 혹은 ’IMPOSSIBLE‘을 출력해주면 됩니다.

문제에서 주어진 예시를 통해 올해의 순위를 구하는 방법을 확인해 보겠습니다.
작년 순위 -> 5 4 3 2 1
바뀐 순위 -> (2, 4), (3, 4)

그렇다면 각 팀이 몇 팀 위에 있는지를 통해 비교해보겠습니다.
작년 -> 5(4팀) 4(3팀) 3(2팀) 2(1팀) 1(0팀)
상대적인 순위가 바뀌었다는 뜻은 (X, Y)일 때, 두 팀 중 높았던 팀은 하나 낮아지고, 낮았던 팀은 하나 올라갔다고 해석이 될 수 있습니다.
따라서 바뀐 순위를 기준으로 다시 정리하면
올해 -> 5(4팀) 4(1팀) 3(3팀) 2(2팀) 1(0팀)
정렬 후-> 5 3 2 4 1

따라서 정답이 나오는 것을 확인 가능합니다.
즉, 팀이 몇 팀 위에 있는지를 확인한 뒤, 등수의 변화를 통해 해당 값을 조정하고 다시 확인하면 순위가 나오게 됩니다.
이때, (X, Y)가 바뀌었다고 하면 둘 중 이전에 높았던 팀이 낮아졌다는 의미가 됩니다.

그렇다면, 나올 수 없는 2가지 경우는 어느 것이냐면
1. 한 순위에 여러팀이 있을 경우 -> 이때가 ‘?’입니다.
2. 다음 순위에 팀이 없어 정할 수 없을 경우 -> 이때가 ‘IMPOSSIBLE’입니다.


먼저, 위의 방법을 통해 자신보다 낮은 팀이 없는 꼴지를 시작으로 한 순위씩 높여가면 되는 것을 알 수 있습니다.
그렇다면, 팀들의 상대적인 높고 낮음을 어떻게 저장하냐가 문제가 됩니다.
저는 2차원 배열을 이용해 [X][Y] = 1이 되면 X가 Y보다 높다 / [X][Y] = -1이 되면 X가 Y보다 낮다로 저장했습니다.

저장한 것을 통해 꼴지팀에서 시작해 자신보다 높은 팀을 찾으면 해당 팀의 값을 1씩 줄여가면서 값이 0이 되는 팀이 생기면
해당 팀을 다음 순위로 생각해 queue에 넣어 해당 팀에서 다시 확인하도록 하면 됩니다.

이때, 다음 단계에 2개 이상의 팀이 생기면 -> ‘?’를, queue가 비어있다면 -> ‘IMPOSSIBLE’을 출력하도록 했습니다.
queue가 비어있으면 탐색을 할 수 없다? -> 위상 정렬은 N번을 반복하기에 for문을 통해 N번의 queue 값이 나올 수 있도록 하면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int test_case;
int N, M;
int ranking[501];
int step[501];
int relation[501][501]; // x가 y보다 큼 -> 1 / 크지 않음 -> -1
int result[501];
bool can_make = true;
queue<int> q;

void reset_array(){
	for(int i = 1; i <= N; i++){
		ranking[i] = 0;
		step[i] = 0;
		result[i] = 0;
		for(int j = 1; j <= N; j++) relation[i][j] = -1;
	}
	can_make = true;
	while(!q.empty()) q.pop();
}

void topological_sort(){
	for(int i = 1; i <= N; i++){
		if(q.empty()){ // 들어갈 값이 없는 경우는 일관성이 없는 데이터가 있는 경우다.
			cout << "IMPOSSIBLE" << "\n";
			can_make = false;
			break;
		}
		if(q.size() > 1){ // 같은 등수가 여러명일 경우는 순위를 정할 수 없다.
			cout << "?" << "\n";
			can_make = false;
			break;
		}
		int x = q.front();
		q.pop();
		result[i] = x;
		for(int j = 1; j <= N; j++){
			if(relation[j][x] == 1){ // j기 x보다 등수가 높을 때
				step[j]--;
				if(step[j] == 0) q.push(j);
			}
		}
	}
}

void solve(){
	for(int i = 1; i <= N; i++){
		if(step[i] == 0) q.push(i);
	}
	topological_sort();
	if(can_make){
		for(int i = N; i >= 1; i--) cout << result[i] << " ";
		cout << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int k = 1; k <= test_case; k++){
		cin >> N;
		reset_array();
		for(int i = 1; i <= N; i++){
			scanf("%d", &ranking[i]);
		}
		for(int i = 1; i <= N; i++){
			for(int j = i + 1; j <= N; j++){
				relation[ranking[i]][ranking[j]] = 1;
				step[ranking[i]]++;
			}
		}
		cin >> M;
		for(int i = 1; i <= M; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			if(relation[x][y] == 1){ // 이전에 x에 y보다 높았을 떄 -> 이제는 y가 더 높다
				relation[x][y] = -1;
				relation[y][x] = 1;
				step[x]--;
				step[y]++;
			}
			else if(relation[x][y] == -1){ // 이전에 x가 y보다 낮았을 때 -> 이제는 x가 더 높다
				relation[x][y] = 1;
				relation[y][x] = -1;
				step[x]++;
				step[y]--;
			}
		}
		solve();
	}
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.