[알고리즘] 위상 정렬

 

위상정렬

위상정렬은 방향성이 있고 사이클이 없는 그래프에서 작업의 순서를 위배하지 않고 정점들을 나열하는 알고리즘이다. 

 

1) 각 노드의 진입 차수(해당 노드로 들어오는 간선 개수)를 계산한다 .

2) 진입 차수가 0인 노드들을 큐에 넣는다.

3) 큐에서 노드를 꺼내고, 해당 노드가 가리키는 모든 인접 노드의 진입 차수를 1 줄인다.

4) 진입 차수가 0이 된 노드는 큐에 다시 넣는다.
모든 노드가 큐에서 한 번씩 빠질 때까지 이 과정을 반복한다.

 

 

예제1) BOJ 2252 줄 세우기

 

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

 

 

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

	int N, M;
	cin >> N >> M;

	vector<vector<int>> graph(N + 1);
	vector<int> indegrees(N + 1, 0);

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		indegrees[b]++;
	}

	queue<int> q;
	for (int i = 1; i < indegrees.size(); i++)
	{
		if (indegrees[i] == 0)
		{
			q.push(i);
		}
	}
	for(int i = 0; i < N; i++)
	{
		int n = q.front();
		q.pop();
		cout << n << ' ';

		for (int m : graph[n])
		{
			indegrees[m]--;
			if (indegrees[m] == 0)
				q.push(m);
		}
	}
}

 

 

예제2) BOJ 1766 문제집

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

 

선행문제는 위상정렬 알고리즘으로 해결, 

이때 쉬운 문제(숫자가 작은 문제)부터 풀어야한다는 조건이 있으므로 pq를 사용했다. 

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

	int N, M;
	cin >> N >> M;

	vector<int> indegrees(N + 1, 0);
	vector<vector<int>> graph(N + 1);

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		indegrees[b]++;
	}

	priority_queue<int, vector<int>, greater<>> q;

	for (int i = 1; i <= N; i++)
	{
		if (indegrees[i] == 0)
			q.push(i);
	}

	while (!q.empty())
	{
		int n = q.top();
		q.pop();
		cout << n << ' ';

		for (int i = 0; i < graph[n].size(); i++)
		{
			int m = graph[n][i];
			indegrees[m]--;

			if (indegrees[m] == 0)
				q.push(m);
		}
	}
}

 

 

 

예제3) BOJ 2056 작업

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

 

이 문제 재밌다. DP + 위상정렬 문제. 

 

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

	int N;
	cin >> N;

	vector<int> indegrees(N + 1, 0);
	vector<int> times(N + 1, 0);
	vector<vector<int>> graph(N + 1);

	for (int i = 0; i < N; i++) {
		int t, n;
		cin >> t >> n;
		times[i + 1] = t;

		for (int j = 0; j < n; j++)
		{
			int a;
			cin >> a;
			graph[a].push_back(i+1);
			indegrees[i+1]++;
		}
	}

	priority_queue<pair<int,int>,vector<pair<int,int>>, greater<>> q; //끝낼 수 있는 최소 시간, 작업
	vector<int> dp(N + 1, 987654321);

	for (int i = 1; i <= N; i++)
	{
		if (indegrees[i] == 0)
		{
			q.push({ times[i], i});
			dp[i] = times[i];
		}
	}

	int n = 0, t = 0;
	indegrees[0] = 1;

	while (!q.empty())
	{
		n = q.top().second;
		t = q.top().first;
		q.pop();

		for (int i = 0; i < graph[n].size(); i++) {
			int next = graph[n][i];
			indegrees[next]--;

			if (indegrees[next] == 0 && t + times[next] < dp[next])
			{
				q.push({ t + times[next], next });
				dp[next] = t + times[next];
			}
		}
	}

	int ans = 0; 
	dp[0] = 0;
	for (int n : dp)
		ans = max(ans, n);
	cout << ans;
}