BOJ 1766 문제집

이 문제를 풀면서 아직 실력이 많이 부족하다는 것을 느꼈다.

처음 생각해낸 방법은 덱을 사용해서 문제마다 모든 조건을 처리해주는 정신 나간 짓을 하려고 하였다.

2번 3번 조건을 만족하기 위해 현재 내가 풀고있는 문제(now)가 있고 이 문제를 풀기 이전 풀어야할 문제(pre)를 설정하고 이상한 뻘짓을 많이 하였다... 

 

문제를 보는 순간 어떤 알고리즘을 물어보는지 감이 오지 않아 어떻게든 내가 알고있는 알고리즘 내에서 최대한 풀어보려고 시도하였다. 또한 문제가 잘 이해되지 않았다. 처음에 답이 두개인가?? 생각도 하고 질문 답변을 확인한 결과 조금 이해가 되었다.

 

어느덧 3시간 고민 후... 각 N 마다 먼저 풀어야하는 문제를 우선순위 큐에 넣어 DFS 탐색까지 도달였다. 하지만 결과는 DFS로는 풀수 없었다. 문제를 완벽하게 이해하지 못하여 정확한 반례를 세우지 못했고 계속 틀렸다.

 

DFS로 풀수 없다는 것을 알게된 후 결국 솔루션을 찾아 보았다. 위상정렬로 한번에 해결 할 수 있었다. 자료구조 그래프 이론 공부가 충분하지 않아 위상 정렬에 대해 찾아보았다.

 

위상정렬(Topological Sort)은 '순서가 정해있는 작업' 차례대로 수행해야 할 때 그 순서를 결정 주기 위해 사용하는 알고리즘이다. 자세한 자료구조 설명은 따로 남길 계획이다.

 

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

vector<int> list[32001];
int entry[32001];

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

	memset(list, 0, sizeof(list));
	memset(entry, 0, sizeof(entry));

	int n, m;
	cin >> n >> m;

	priority_queue<int, vector<int>, greater<int>> pq;
	
	for(int i = 0; i < m; i++)
	{
		int pre, now;

		cin >> pre >> now;
		list[pre].push_back(now);
		entry[now]++;
	}


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

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

		for(int j = 0; j < list[num].size(); j++)
		{
			int next = list[num][j];
			entry[next]--;

			if(entry[next] == 0) pq.push(next);
		}
		cout << num << " ";
	}
}