백준 15758 : Milking Order

문제 링크

N 마리의 소가 있고, M개의 우유 먹는 순서가 주어졌을 때, 모순이 생기기 직전까지의 순서를 기준으로하여 가능한 순서중 가장 사전순으로 빠른 순서를 출력하는 문제였다.
문제의 정해는 모순이 생기는 지점 X를 이분탐색을 통해 찾고, 그 X까지의 간선정보를 이용하여, queue가 아닌 priority queue를 이용해 사전순으로 정렬을 하는 것이었다.

결론적으로는 풀이를 봤다. 모순이 생기는 지점 X를 찾는데에 이분탐색을 떠올린 데까지는 좋았는데, Edge를 갱신하는데 O(E)만큼의 시간의 들고, 이분탐색은 O(logn)이기 때문에 시간초과가 날 필요가 없는데 계속 시간초과가 나서 멘탈이 터졌다... 이것저것 만져도 해결되지도 않고 결국 풀이를 보고서도 한참을 찾았는데, 입력을 받을때 m개가 아닌 n개를 받고, 순서를 저장해놓은 order배열도 크기를 n으로 저장해놓은것이 문제였다.

풀이를 봤더니 이번엔 사전순 정렬쪽이 문제였다. 일반적인 queue로 정렬하면서 가능한 것들중 사전순으로 앞선것들을 앞에 끼워넣으려고 했는데, 생각해보면 풀이에 나온 priority queue만큼 적절한 게 없었다. 이걸 생각을 왜 못했을까. ㅠ 잘 알아놔야겠다. priority queue는 진짜 생각치도 못했던 곳에서 많이 쓰게 된다.

결국 priority_queue로 고치고.. 또 한참을 보고 입력 문제 고치고해서 AC를 받았지만, 이것저것 건드리면서 코드도 더러워지고, 풀면서 멘탈도 너덜너덜해졌던 문제였다.

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

using namespace std;

typedef pair<int,int> pii;

int n,m;

vector<vector<int>> order;
vector<vector<int>> edge;
vector<bool> finished;
vector<int> discovered;
vector<int> indeg;
vector<int> tempindeg;

bool iscycle = false;
int discovercnt = 0;

void appendedge(const vector<int>& vec)
{
	int vecsize = vec.size();

	if(vecsize <= 1) return;
	for(int i = 0;i<vecsize-1;i++)
	{
		edge[vec[i]].push_back(vec[i+1]);
	}
}

void clearedge(const vector<int>& vec)
{
	int vecsize = vec.size();
	
	for(int i = 0;i<vecsize-1;i++)
	{
		edge[vec[i]].pop_back();
	}
}

bool isvalid()
{
	tempindeg = vector<int>(n,0);
		
	for(int i = 0;i<n;i++)
	{
		for(auto next : edge[i])
		{
			tempindeg[next]++;
		}
	}
	
	vector<int> topolo;
	queue<int> q;
	for(int i = 0;i<n;i++)
	{
		if(!tempindeg[i]) q.push(i);
	}
	
	while(!q.empty())
	{
		int cur = q.front();
		q.pop();
		topolo.push_back(cur);
		
		for(auto next : edge[cur])
		{
			if((--tempindeg[next]) == 0) q.push(next);
		}
	}
	
	return topolo.size() == n;
}

int nocyclelimit(int s,int e)
{
//	cout<<s<<" "<<e<<" ";
	
	if(s >= e) return e;
	edge = vector<vector<int>>(n);
	int m = (s+e)/2;
//	cout<<m<<endl;
	for(int i = 0;i<=m;i++)
	{
		appendedge(order[i]);
	}
	
	if(s == e-1)
	{
		appendedge(order[e]);
		
		if(isvalid()) return e;
		else
		{
			clearedge(order[e]);
			return s;	
		}
		
	}
	
	if(isvalid()) return nocyclelimit(m,e);
	else return nocyclelimit(s,m-1);
	
}

int main(int argc, char** argv) {
	scanf("%d %d",&n,&m);
	
	order = vector<vector<int>>(m);
	
	for(int i = 0;i<m;i++)
	{
		int cnt;
		scanf("%d",&cnt);
		
		for(int j = 0;j<cnt;j++)
		{
			int ord;
			scanf("%d",&ord);
			
			ord--;
			order[i].push_back(ord);
		}
	}
	
	int lim = nocyclelimit(0,m-1);
	edge = vector<vector<int>>(n);
	
	for(int i = 0;i<=lim;i++)
	{
		appendedge(order[i]);
	}
	vector<int> indeg(n,0);

	for(int i = 0;i<n;i++)
	{
		sort(edge[i].begin(),edge[i].end());
		
		for(auto next : edge[i])
		{
			indeg[next]++;
		}
	}
	
	priority_queue<int,vector<int>,greater<int>> pq;
	vector<int> ans;
	
	for(int i = 0;i<n;i++)
	{
		if(!indeg[i]) 
		{
			pq.push(i);
		}
	}
	
	
	while(!pq.empty())
	{
		int cur = pq.top();
		pq.pop();
		
		ans.push_back(cur);
				
		for(auto next : edge[cur])
		{
			if((--indeg[next]) == 0) pq.push(next);
		}
	}
	
	
	
	
	for(auto elem : ans)
	{
		printf("%d ",elem+1);
	}
	return 0;
}