[백준 C++] 1766번: 문제집

1. 문제

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

1766번: 문제집

 

2. 알고리즘 분류

• 자료 구조
• 그래프 이론
• 우선순위 큐
• 위상 정렬
• 방향 비순환 그래프

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_N 32001

using namespace std;

int N, M;
int visited[MAX_N];
int inDegree[MAX_N];
vector<int> graph[MAX_N];
vector<int> path;

// 위상정렬
void topologicalSort()
{
	// 모든 노드 탐색
	for (int i = 1; i <= N; i++)
	{
		// 진입차수가 0이 아니거나, 이미 방문한 노드이면 건너뛰기
		if (inDegree[i] || visited[i]) continue;

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

		visited[i] = 1;	// 방문 체크
		q.push(i); // Queue에 추가

		// Queue 탐색
		while (!q.empty())
		{
			int cur = q.top();
			q.pop();	
			path.push_back(cur);	// 경로 추가

			// 해당 노드의 간선 탐색
			for (int j = 0; j < graph[cur].size(); j++)
			{
				int next = graph[cur][j];

				// 이미 방문했거나, 차감한 진입차수가 0이 아니면 건너뛰기
				if (visited[next] || --inDegree[next] != 0) continue;

				visited[next] = 1;	// 방문 체크
				q.push(next);	// Queue에 추가
			}
		}
	}
}

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 문제의 수, M : 정보의 개수
	cin >> N >> M;

	// 정보들 입력
	for (int i = 0; i < M; i++) 
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);	// 그래프 추가
		inDegree[b]++;	// 진입차수 추가
	}

	// 위상정렬 알고리즘
	topologicalSort();

	// 정답 출력
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << " ";

	return 0;
}

 

4. 유용한 알고리즘

1) 위상 정렬

1. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘
2. 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행
3. 시간 복잡도 = O(V + E)

https://uigwonblog.tistory.com/50

[알고리즘] 위상 정렬(Topological Sorting)