위상정렬을 이용한 백준 2252, 1766 문제풀이

줄 세우기 , 문제집

줄 세우기는 위상 정렬을 알고 있다면 풀 수 있는 문제이고, 문제집은 위상정렬을 조금 변형한 문제이다.

먼저 위상 정렬에 대해 알아보자.

배경지식

그래프 탐색은 내가 원하는 곳을 중복하지 않고 한번씩 방문하는 것이다. 여기서 두 가지 방법으로 나뉜다.

1. DFS(깊이 우선 탐색)
2. BFS(너비 우선 탐색)

깊이 우선 탐색은 처음 정점에서 방문할 수 있는 한 최대의 깊이를 방문한 뒤, 그 다음 정점을 보는 방식이고,

너비 우선 탐색은 처음 정점에서 연결된 정점들을 방문한 뒤 깊이가 하나 더한 정점들을 살펴보는 방식이다.

DFS와 BFS를 그림으로 쉽게 설명한 글들이 많다. 그런 글을 먼저 보고 오자.

위상정렬

위상 정렬이란 그래프 간선의 우선순위가 주어질 때 정점의 순서를 찾는 알고리즘이다.

즉, 2보다 1이 먼저와야 한다고 하면 그 순서를 지키면 된다.

BFS와 DFS를 알고 있다면 거기에 아주 약간의 지식만 더 추가하면 된다.

1. 위상정렬을 하려면 사이클이 없어야 한다.
2. 간선이 도착하는 횟수를 저장하는 배열을 만들고 그 값이 __0일때__만 실행하면 된다.

왜?

간선이 도착하는 횟수가 제일 처음에 0인 경우는 시작점이라는 것을 알려주고,

그 간선을 사용할 때마다 -1을 해주면 이전 노드에 방문했다는 것을 의미한다.

반대로 횟수가 0이 아닌 경우엔, 이전 노드가 아직 존재한다는 것이므로 정점 방문을 실행하지 않는다.

줄 세우기

위의 정보들을 이용하여 코드를 작성해 보자.

나의 경우엔 bfs를 사용하여 코드를 작성해 보았다.

위상 정렬 개념 문제기 때문에 위상 정렬을 코드화한 것으로도 맞게 된다.

문제집

위상정렬을 한 것 중에서 가장 작은 수가 먼저 나와야 하는데,

큐에 가장 작은 값을 pop해야 한다.

아주 간단한 방법으로는 minimum heap을 사용하는 방법이 있다.

STL에는 priority_queue라는 간편한 힙이 있다.

queue<int> q;
# 위 코드 한줄을 밑의 코드로 바꾸면 문제집 코드가 된다.
#priority_queue<int>는 내림차순이며, 오름차순으로 바꾸려면 greater 인자를 추가해주면 된다.
priority_queue<int,vector<int>,greater<int>> q;

줄 세우기 소스

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	int topo[32001] = { 0 };
	cin >> n >> m;
	vector<int> adj[32001];
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		topo[b]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (topo[i] == 0)
			q.push(i);
	}
	while (!q.empty()) {
		int t = q.top(); q.pop();
		cout << t<<' ';
		for (auto tt : adj[t]) {
			topo[tt]--;
			if (topo[tt] == 0)
			{
				q.push(tt);
			}
		}
	}
}

문제집 소스

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	int topo[32001] = { 0 };
	cin >> n >> m;
	vector<int> adj[32001];
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		topo[b]++;
	}
	priority_queue<int,vector<int>,greater<int>> q;
	for (int i = 1; i <= n; i++) {
		if (topo[i] == 0)
			q.push(i);
	}
	while (!q.empty()) {
		int t = q.top(); q.pop();
		cout << t<<' ';
		for (auto tt : adj[t]) {
			topo[tt]--;
			if (topo[tt] == 0)
			{
				q.push(tt);
			}
		}
	}
}