백준 1432 그래프 수정

백준 1432
위상 정렬로 풀면 된다. 그런데 특이한 점은 보통의 위상정렬(in degree 0인 정점부터 제거)가 아닌, 리버스(?) 위상 정렬로 풀어야 한다.(out degree 0인 정점부터 제거)
처음엔 이 둘의 결과가 차이난다는 것을(단순히 순서가 뒤집히는 정도가 아니다) 납득하지 못해 직접 테스트 케이스를 생성해 결과까지 대조해봤다.

처음 소스(보통의 위상 정렬)

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

vector<int> adj[301];
int ind[301];
int ans[301];

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		string cur;
		cin >> cur;
		for (int k = 1; k <= N; k++) if (cur[k - 1] == '1') {
			adj[i].push_back(k);
			ind[k]++;
		}
	}

	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 1; i <= N; i++) if (ind[i] == 0) {
		pq.push(i);
	}
	
	int m = 0;
	while (!(pq.empty())) {
		int cur = pq.top(); pq.pop();
		ans[cur] = ++m;
		
		for (int next : adj[cur]) {
			ind[next]--;
			if (ind[next] == 0) {
				pq.push(next);
			}
		}
	}
	
	if (m != N) {
		cout << -1;
		return 0;
	}

	for (int i = 1; i <= N; i++) {
		cout << ans[i] << ' ';
	}

	return 0;
}

도저히 맞는 것 같은데 CA가 안뜨길레
정답이라도 알아야 겠다 싶어서 인터넷 찬스를 써봤다.
https://fatc.club/2017/03/01/397

위 링크를 참조한 수정 코드(CA가 떴다)
차이점은, 처음 그래프를 만들 때 간선 방향을 모두 반대로 해서 넣어줬다.(그렇게 하면 indegree가 outdegree가 된다.) 그리고 우선순위 큐도 큰 값을 먼저 뱉는다.
그리고 그 상태로 위상 정렬을 하면 리버스(?) 위상 정렬이 되는데, 이 때도 순열 값을(M1~MN) 올림차순(++m)이 아니라 내림차순(m–)으로 넣어줬다.
한마디로 위상 정렬도 거꾸로 하는 대신 순열 값도 거꾸로 내림차순으로 넣어줬다.
처음에는 이 둘의 결과가 같을 줄 알았다. 근데 아니었다….

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

vector<int> adj[301];
int ind[301];
int ans[301];

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		string cur;
		cin >> cur;
		for (int k = 1; k <= N; k++) if (cur[k - 1] == '1') {
			adj[k].push_back(i);
			ind[i]++;
		}
	}

	priority_queue<int> pq;

	for (int i = 1; i <= N; i++) if (ind[i] == 0) {
		pq.push(i);
	}

	int m = N;
	while (!(pq.empty())) {
		int cur = pq.top(); pq.pop();
		ans[cur] = m--;

		for (int next : adj[cur]) {
			ind[next]--;
			if (ind[next] == 0) {
				pq.push(next);
			}
		}
	}

	if (m != 0) {
		cout << -1;
		return 0;
	}

	for (int i = 1; i <= N; i++) {
		cout << ans[i] << ' ';
	}

	/*for (int i = 1; i <= N; i++) {
	for (int k = 1; k <= N; k++) {
	cout << adj[i][k] << ' ';
	}
	cout << endl;
	}*/

	return 0;
}

너무나도 이해가 안간 나머지 고민을 많이 했는데, 이럴 바에야 몸이 고생해서 직접 브루트 포스로 확인해보자 싶었다. 따라서, 테스트 케이스를 랜덤으로 생성해서 두 알고리즘에 나란히 적용하고, 두 알고리즘의 결과가 다른 케이스를 발견할 때까지 무작정 반복. 오래 걸릴 줄 알았는데, 이외로 정점 4개짜리 간단한 그래프를 발견했다. 일단 아래는 테스트를 위한 소스코드. 개념을 이해하지 못해 몸으로 때운 흔적이다(…)

그에 앞서 발견한 반례를 공개한다.

4
0011
0000
0000
0100

기존 알고리즘의 결과 : 1 4 2 3
참고해 고친 알고리즘의 결과(정답) : 1 3 4 2

간선 3개짜리 간단한 그래프이나, 두 알고리즘의 차이점을 알 수 있었다.
기존 알고리즘은 1정점을 먼저 취하고, 그로 인해 indegree=0인 정점 두개(3,4)가 남았을 때 greedy하게 3을 택하는 바람에 2정점의 순서가 뒤로 밀려 버렸다. 사전 순서로 첫번째인 순열을 출력했어야 하는데 이렇듯 순서가 뒤로 밀려버리니….
그에 반해 고친 알고리즘은 outdegree=0인 정점(2,3)부터 취하는데, 이 때 큰 값부터 우선순위 큐가 뱉어주므로 3정점을 취한다. 그리고 3정점은 가장 큰 번호를 배정해준다.(N=4) 그 다음 outdegree=0인 정점은 2정점 밖에 없으므로 그 다음 값인 3을 배정해준다. 비록 두번째로 큰 번호를 배정받긴 했지만 최적값임에 놀랐다. 그 다음 차례대로 4정점 1정점 순으로 점점 작은 번호를 배정해준다.

참 동일한 알고리즘이라 생각했는데 그게 아니었다는 게 신기했다..

#include <iostream>
#include <functional>
#include <string>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

vector<int> adj[301], adj2[301];
int ind[301], ind2[301];
int ans[301], ans2[301];

bool f(int N) {
	fill(adj, adj + N, vector<int>());
	fill(ind, ind + N, 0);
	fill(ans, ans + N, 0);
	fill(adj2, adj2 + N, vector<int>());
	fill(ind2, ind2 + N, 0);
	fill(ans2, ans2 + N, 0);


	int test[301][301];
	for (int i = 1; i <= N; i++) {
		test[i][i] = 0;
		for (int k = i + 1; k <= N; k++) {
			int tmp = rand() % 2;
			test[i][k] = tmp;
			test[k][i] = (tmp == 0 && rand() % 2 == 1)? 1 : 0;
		}
	}


	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) if(test[i][k] == 1){
			adj[k].push_back(i);
			ind[i]++;

			adj2[i].push_back(k);
			ind2[k]++;
		}
	}

	priority_queue<int> pq;

	for (int i = 1; i <= N; i++) if (ind[i] == 0) {
		pq.push(i);
	}

	int m = N;
	while (!(pq.empty())) {
		int cur = pq.top(); pq.pop();
		ans[cur] = m--;

		for (int next : adj[cur]) {
			ind[next]--;
			if (ind[next] == 0) {
				pq.push(next);
			}
		}
	}


	priority_queue<int, vector<int>, greater<int>> pq2;

	for (int i = 1; i <= N; i++) if (ind2[i] == 0) {
		pq2.push(i);
	}

	int m2 = 0;
	while (!(pq2.empty())) {
		int cur = pq2.top(); pq2.pop();
		ans2[cur] = ++m2;

		for (int next : adj2[cur]) {
			ind2[next]--;
			if (ind2[next] == 0) {
				pq2.push(next);
			}
		}
	}
	bool firstNeg = m != 0, secondNeg = m2 != N;
	if (firstNeg && secondNeg) {
		return true;
	}
	else if (firstNeg) {
		return false;
	}
	else if (secondNeg) {
		return false;
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (ans[i] != ans2[i]) {
				return false;
			}
		}
		return true;
	}
}


int main() {

	srand(time(0));
	int K = 5;
	while(1)
		cout << (f(rand()%K + 1) ? " " : "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXx");
	

	return 0;
}

출력 기능이 있지만, 실제로는 false값을 리턴하는 지점에 중단점을 설정하고 변수 모니터로 로컬 변수 값(테스트 케이스 값)을 확인하는 방식을 취했다.
순열이 없는 경우(사이클이 있는 경우;-1출력)에서 틀리지 않았으리라고 생각했기 때문에, 적어도 길이 2 이하의 사이클은 배제한 테스트 케이스만 사용했다. (그 정도 조건은 구현이 간단하기도 하고)