BOJ 백준 1766 문제집 <위상정렬>

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

<문제집>

 어떤 문제를 풀기 위해서 다른 문제를 먼저 풀어야 하는, 일반적인 위상정렬 문제이다.

다만, 가장 쉬운 문제부터 풀어야한다는 조건이 있다. 정점의 번호순으로 1번부터 N번으로 가면서 점점 어려워진다.

예를 들어,

1. 4번 문제를 풀기 위해서는 2번 문제를 먼저 풀어야 한다.                 2 -> 4

2. 1번 문제를 풀기 위해서는 3번 문제를 먼저 풀어야 한다.                 3 -> 1

위의 두 가지 조건이 있을 때 답은

2 -> 3 -> 1 -> 4 가 된다.

2번을 푼 뒤에 풀 수 있는 문제는 3번과 4번 문제인데, 3번이 더 쉬우므로 3번을 풀고 그 다음엔 1번과 4번을 비교하여 1번을 먼저 푸는 것이다.

이러한 문제는 DFS로 풀 수 없다고 생각하여 indgree 배열을 이용한 풀이를 하였다.

먼저 단순하게 푼 풀이는, 매번 가장 쉬운 문제의 번호를 계산해주면서 푸는 것이다. 이는 매번 최대 N번씩 검사해야 하므로 비효율적이다.

따라서 우선순위 큐를 이용하여 정점의 번호를 오름차순으로 저장해주면서 푸는 것이 좋다.

1. 단순 풀이 ( 매번 계산 )

#include <iostream>
#include <vector>
#include <queue>
#define SIZE 32001

using namespace std;
int n, m;
int idg[SIZE];
int seq[SIZE];
int seq_idx = 0;
vector<int> vtx[SIZE];

int get_min_node()
{
	for (int i = 1; i <= n; ++i)
	{
		if (idg[i] == 0)
			return i;
	}
	return -1;
}

void solution()
{
	while (1)
	{
		int v = get_min_node();
		if (v == -1) break;
		seq[seq_idx++] = v;

		idg[v] = -1;
		
		for (int x : vtx[v])
		{
			--idg[x];
		}
	}

	for (int i = 0; i <= seq_idx - 1; ++i)
	{
		cout << seq[i] << " ";
	}
}

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

	cin >> n >> m;

	queue<int> q;

	vtx->resize(n + 1);
	for (int i = 0; i < m; ++i)
	{
		int front, back;
		cin >> front >> back;

		vtx[front].push_back(back);
		idg[back]++;
	}
	solution();

	return 0;
}

2. 우선순위 큐를 이용한 풀이

#include <iostream>
#include <vector>
#include <queue>
#define SIZE 32001

using namespace std;
int n, m;
int idg[SIZE];
int seq[SIZE];
int seq_idx = 0;
vector<int> vtx[SIZE];

void solution()
{
	priority_queue< int, vector<int>, greater<int> > pq;

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

	while (!pq.empty())
	{
		int v = pq.top();
		pq.pop();
		seq[seq_idx++] = v;

		for (int x : vtx[v])
		{
			if ((--idg[x]) == 0)
				pq.push(x);
		}
	}
	for (int i = 0; i < seq_idx; ++i)
	{
		cout << seq[i] << " ";
	}
}

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

	cin >> n >> m;

	queue<int> q;

	vtx->resize(n + 1);
	for (int i = 0; i < m; ++i)
	{
		int front, back;
		cin >> front >> back;

		vtx[front].push_back(back);
		idg[back]++;
	}
	solution();

	return 0;
}