백준/2252/toplogical sort/줄 세우기

백준/2252/toplogical sort/줄 세우기
toplogical 문제로 두 사람의 키를 비교해서 차례대로 세우는 문제입니다.

vector<int> adj[32001];
queue<int> q;
int deg[32001];
vector<int>result;

위에서부터 adj는 인덱스가 선수 요소를 뜻하고 해당 요소를 선수 요소로 두는 요소들을 저장한다.
queue는 해당 선수 요소의 indegree에 수가 0일 경우 담아낼 큐이다.
deg int 배열은 인덱스가 선수 요소를 뜻하고 해당 요소의 indegree의 수를 담고 있다.
result는 그렇게 나열 된 요소를 저장하는 vector이다.

  for (int i = 0; i < M; i++) {
		for (int j = 0; j < 2; j++) {
			cin >> arr[j];
		}
		adj[arr[0]].push_back(arr[1]);
		deg[arr[1]]++;
	}	

위에는 선수 요소를 지목될 요소와 선수 요소를 필요로하는 요소를 arr에 입력받고
처음에 나온 요소가 선수 요소이니 해당 선수 요소(arr[0])를 인덱스로 하는 adj배열에 선수 요소(arr[0])를 필요로 하는 요소(arr[1])를 push_back해준다.
그 이후 해당 요소(arr[1])는 선수 요소가 하나 필요한 것이니 degree를 증가시켜준다.

	for (int i = 1; i <= N; i++) {
		if (deg[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		result.push_back(cur);
		for (auto x : adj[cur]) {
			deg[x]--;
			if (deg[x] == 0)q.push(x);
		}
	}

그 다음 indegree가 0인 선수 요소들을 먼저 넣고 toplogical sort를 해준다.

  	if (result.size() != N) {
		cout << "cycle has been exisited";
	}
	else {
		for (auto x : result) cout << x << " ";
	}

result안의 size가 모든 요소를 포함하고 있으면 정확히 toplogical sort를 해준것이므로 통과 시킨 뒤 result vector 값을 출력하고
그렇지 않을 시 해당 요소에 진입 요소가 없는 cycle이 존재하는 graph가 되므로 오류 문구를 출력하고 종료시킨다.

풀이

1. 첫번째 풀이

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

vector<int> adj[32001];
queue<int> q;

int deg[32001];
vector<int>result;

int main(void) {
	int arr[2];
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 2; j++) {
			cin >> arr[j];
		}
		adj[arr[0]].push_back(arr[1]);
		deg[arr[1]]++;
	}	


	for (int i = 1; i <= N; i++) {
		if (deg[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		result.push_back(cur);
		for (auto x : adj[cur]) {
			deg[x]--;
			if (deg[x] == 0)q.push(x);
		}
	}


	if (result.size() != N) {
		cout << "cycle has been exisited";
	}
	else {
		for (auto x : result) cout << x << " ";
	}

}

2. 두번째 풀이(모듈화)

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

vector<int> adj[32001];
vector<int> result;
queue<int>q;

int deg[32001];
int N, M;
int arr[2];

void solution();
void func();

void func() {
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 2; j++) {
			cin >> arr[j];
		}
		adj[arr[0]].push_back(arr[1]);
		deg[arr[1]]++;
	}
	for (int i = 1; i <= N; i++)
		if (deg[i] == 0)q.push(i);
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		result.push_back(cur);
		for (auto x : adj[cur]) {
			deg[x]--;
			if (deg[x] == 0)q.push(x);
		}
	}
	solution();
}

void solution() {
	for (auto x : result)cout << x << ' ';
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	func();
}