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

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

1766번: 문제집

백준 1766번 문제집 문제를 풀었다.

 

위상 정렬 문제를 처음 풀어봤다. 이 문제 처럼 순서가 정해져 있는 작업을 수행할 때 그 순서를 결정해주는 알고리즘이라고 한다. 아래의 블로그를 참고했다.

https://yoongrammer.tistory.com/86

 

adjList 배열은 인접리스트를 저장하는 배열이다.

in_degree 배열은 본인에게 들어오는 화살표의 개수를 저장한다.

pq 는 우선순위 큐인데, 가능하면 쉬운 문제부터 푸는 조건을 만족하기 위해 사용했다.

ans 는 정답을 저장한다.

 

먼저 문제의 입력을 받으면서 인접리스트와 in_degree 배열을 채운다.

in_degree 배열을 순회하면서 값이 0인 노드들을 우선순위 큐에 넣는다.

그 다음 위상정렬을 실행하는데, 우선순위 큐가 빌 때까지 아래의 작업을 반복한다.

1. 우선순위 큐의 맨 위 원소를 cur 변수에 보관하고 ans에 넣는다.

2. 우선순위 큐의 맨 위 원소를 pop한다.

3. cur 노드와 인접한 노드를 순회하면서 아래의 작업을 반복한다.

3.1 next 변수에 cur 노드와 인접한 노드를 보관한다.

3.2 next의 in_degree를 하나 감소시킨다.

3.3 next의 in_degree가 0이라면 우선순위 큐에 넣는다.

 

위상 정렬을 실행하고 나면 ans에 문제를 푸는 순서가 저장된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

struct compare {
	bool operator()(int a, int b) {
		return a > b;
	}
};

int n, m;
vector<int> adjList[32001];
int in_degree[32001];
priority_queue<int,vector<int>,compare> pq;
vector<int> ans;

void TopologicalSort() {
	while (!pq.empty()) {
		int cur = pq.top();
		ans.push_back(cur);
		pq.pop();

		for (int i = 0; i < adjList[cur].size(); i++) {
			int next = adjList[cur][i];
			in_degree[next]--;
			if (in_degree[next] == 0) {
				pq.push(next);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end;
		scanf("%d %d", &start, &end);
		adjList[start].push_back(end);
		in_degree[end]++;
	}

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

	TopologicalSort();

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}

	return 0;
}