백준 3665 최종순위

풀이는 다음과 같다.

팀을 vertex, 팀의 우열관계를 edge로 하여 방향그래프를 만든다. 

이때 주의할 점은 가능한 모든 edge를 다 넣는 것이다.

예를 들어, 4 3 2 1이 주어졌다고 하자(팀4가 1등, 팀1이 4등)

그렇다면 방향그래프는 

4 -> 3

4 -> 2

4 -> 1

3 -> 2

3 -> 1

2 -> 1

와 같이 6개의 edge로 구성되어 있어야 한다.

그 후 팀의 우선순위가 바뀌는 쌍을 입력받는다.

이 쌍은 방향이 바뀌는 edge의 노드 쌍이다.

예를 들어, 위와 같은 그래프일때

(4, 1)

(3, 2)

를 입력받았다면

4 -> 3

4 -> 2

4 <- 1 : 방향 바뀜

3 <- 2 : 방향 바뀜

3 -> 1

2 -> 1

와 같은 그래프로 바뀐다

그 후, 이 그래프를 위상정렬을 하여 팀의 등수를 나타내는 것이 이 문제의 풀이이다.

From노드로부터 To노드로 연결되어 있는지 빠르게 알기 위해서 adj배열은 2차원 배열을 활용했고,

진입 차수는 inDegree배열을 미리 만들고, 입력이 들어올 때 같이 전처리 하였다.

다음은 특이사항이다.

1. 입력이 많아 보여서 scanf로 받았다.

2. 위상정렬은 queue와 1차원 배열로 했다.

queue는 진입차수가 0인 노드가 들어가는 자료구조,

배열은 위상정렬의 결과값이 들어가는 자료구조이다.

위상정렬 알고리즘은 간략하게 다음과 같다.

##

진입차수가 0인 노드를 queue에 넣고,

queue에서 노드 하나를 빼고(노드 n이라고 하자.),

노드n을 1차원 배열에 넣는다.

그 후 노드 n에서 진입하는 노드들의 inDegree를 1씩 줄인다. (예를 들어, 위와같은 그래프에서 노드 n이 2일 경우, 1의 inDegree가 줄어든다.)

또한 inDegree[n]을 1을 줄이지 않으면 다음 루프에서 이 inDegree도 0이기 때문에 queue에 넣는 문제가 발생한다. 따라서 inDegree[n]도 1씩 줄인다.

##

3. IMPOSSIBLE의 결과가 나오는 경우는 그래프에 Cycle이 있는 경우이다.

그런데 위상정렬을 할 때 Cycle이 있는 경우를 어떻게 체크할까?

바로 queue에 아무것도 들어가지 않을 때이다.

이유는 다음과 같다.

##

queue에 노드가 들어간다는 뜻은?

노드의 진입차수가 0이라는 뜻이다.

그런데 사이클을 만나게 되면?

진입차수가 0인 노드가 없다.

따라서 queue에 넣을 노드가 없으면 사이클이 있다는 뜻이다.

##

방향그래프에서 사이클을 찾을때 DFS를 이용하면 고려할게 너무 많아진다.

그래서 DFS를 사용하는 것보다 위상정렬이 훨신 알고리즘도 편하고 빨리 짤수 있으니, 방향그래프에서는 위상정렬을 쓰는걸 항상 고려하자.

(이것 때문에 한번 틀렸다. 방향 그래프에서도 무방향 그래프처럼 DFS로 대충 탐색하다가 대충 틀렸다..)

4. "?"의 결과가 나오는 경우는 그래프에서 진입차수가 0인 노드가 한개가 아니라는 뜻이다.

예를 들어,

탐색을 시작하는 노드는 항상 1등 노드에서 시작한다.

그리고 1등 노드란 진입차수가 처음부터 0인 노드이다.

그런데 진입차수가 0인 노드가 여러개라면?

1등 노드가 여러개라고 판단이 되기 때문에 ?를 출력해야 한다.

그렇다면 진입차수가 0인 노드가 여러개인 것을 어떻게 판단하느냐

그건 바로 queue의 사이즈가 1을 초과하는지 체크하면 된다.

따라서 아래와 같은 코드가 나온다.

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS

#include <iostream> 
#include <vector> 
#include <queue> 
#include <stack>
#include <fstream> 
#include <string> 
#include <algorithm>

using namespace std;

int testcase;
int N, M;
bool adj[501][501];
int score[501];
int result[501];
int inDegree[501];

int main() {
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &N);
		for (int i = 0; i < N; i++) {
			scanf("%d", &score[i]);
			score[i]--;
			result[i] = -1;
			inDegree[i] = 0;
			for (int j = 0; j < N; j++) {
				adj[i][j] = false;
			}
		}

		for (int i = 0; i < N; i++) {
			int start = score[i];
			for (int j = i + 1 ; j < N; j++) {
				adj[start][score[j]] = true;
				inDegree[score[j]]++;
			}
		}

		scanf("%d", &M);

		for (int i = 0; i < M; i++) {
			int from, to;
			scanf("%d %d", &from, &to);
			from--;
			to--;
			if (adj[from][to]) {
				adj[from][to] = false;
				adj[to][from] = true;
				inDegree[to]--;
				inDegree[from]++;
			}
			else {
				adj[to][from] = false;
				adj[from][to] = true;
				inDegree[from]--;
				inDegree[to]++;
			}
		}
		
		queue<int> resultQ;
		for (int i = 0; i < N; i++) {
			if(inDegree[i] == 0) resultQ.push(i);
		}

		for (int loop = 0; loop < N; loop++) {
			if (resultQ.empty()) {
				cout << "IMPOSSIBLE" << endl;
				goto ENDLOOP;
			}
			if (resultQ.size() > 1) {
				cout << "?" << endl;
				goto ENDLOOP;
			}
			int now = resultQ.front();
			result[loop] = now;
			resultQ.pop();
			inDegree[now]--;
			for (int i = 0; i < N; i++) {
				if (adj[now][i]) inDegree[i]--;
				if (inDegree[i] == 0) resultQ.push(i);
			}
		}

		for (int i = 0; i < N; i++) {
			cout << result[i] + 1 << " ";
		}
		cout << endl;

	ENDLOOP:;

	}


	return 0;
}