[백준/BOJ] 백준 15758번 : Milking Order

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

15758번: Milking Order

 

최대 어떠한 규칙까지 지킬 수 있는지 이분탐색을 통해 확인했고, 규칙이 지켜지는지 여부는 위상정렬로 순서가 만들어지는지를 통해 확인했다. 이때, 사용하는 큐는 같은 조건에서 낮은 번호가 먼저 나오도록 우선순위 큐를 사용했다.

 

코드

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

int n, m;
vector<int> order[50005];
vector<int> result;

//0번 규칙에서 point번 규칙까지 모두 지킬 수 있는지 확인
bool check(int point) {

	vector<int> adj[100005];
	vector<int> indegree(100005, 0);
	priority_queue<int> pq;

	for (int i = 0; i <= point; i++) {

		for (int j = 1; j < order[i].size(); j++) {
			int before = order[i][j - 1];
			int here = order[i][j];

			adj[before].push_back(here);
			indegree[here]++;
		}
	}

	//위상 정렬을 통해 순서가 만들어지는지 확인한다
	//순서를 만들때 같은 조건에서 낮은 번호가 먼저 나오도록 우선순위 큐를 사용한다
	vector<int> temp_result;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			pq.push(-i);
		}
	}

	while (!pq.empty()) {
		int here = -pq.top();
		pq.pop();

		temp_result.push_back(here);

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];

			indegree[there]--;

			if (indegree[there] == 0) {
				pq.push(-there);
			}
		}
	}

	if (temp_result.size() == n) {
		result = temp_result;
		return true;
	}

	return false;
}

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

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int cnt;
		cin >> cnt;
		for (int j = 0; j < cnt; j++) {
			int input;
			cin >> input;

			order[i].push_back(input);
		}
	}

	//어떠한 규칙까지 지킬 수 있는지 이분 탐색을 통해 확인한다
	int left = 0;
	int right = m - 1;
	while (left <= right) {
		int mid = (left + right) / 2;

		if (check(mid)) {
			left = mid + 1;
		}

		else {
			right = mid - 1;
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}

	return 0;
}