[백준 BOJ 1766 gold2 - 문제집] 위상정렬(topological sort) , 우선순위 큐(priority queue) C++

백준 문제집 1766

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

1766번: 문제집

 

1부터 N까지의 문제를 푸는 순서를 출력한다.

조건은 두가지다.

1. 되도록 쉬운 문제 먼저 푼다.(작은 숫자 문제 먼저 풀어야 한다)

2. 먼저 푸는 문제가 있으면 먼저 풀어야 한다. (두 문제 간에 우선순위가 있다.)

 

문제 간의 우선순위를 지키면서, 쉬운문제를 풀어야 한다.

1번조건을 충족하기 위해서 우선순위 큐를 사용하고, 2번 조건은 위상 정렬을 떠올려야 한다.

이 두개를 떠올렸다면 엄청 쉽게 풀 수 있는 문제였다

 

알고리즘 들을 때 위상정렬 다 배웠는데 처음에 문제보고는 아예 떠올리지를 못했다.....

진짜 멀었다 ㅎㅎ... 열심히 해야지 ,,

 

위상정렬 알고리즘

사이클이 없고, directed graph여야 한다. (DAG)

각 노드별로 들어오는 edge개수를 저장한다(indegree)

 

1. indegree[k] 가 0 인 노드를 queue에 넣는다. (이 문제의 경우에는 priority queue)

2. queue를 돌면서, top을 pop하고, top이 가리키는 edge를 다 삭제한다. (indegree가 0 이 되는 노드가 생기면 queue에 push한다.) 

3. 반복...

 

	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		degree[b]++;
	}

	for (int i = 1; i <= N; i++) {
		if (degree[i] == 0) {
			pq.push(-i);
		}
	}

	while (!pq.empty()) {
		int top = -pq.top();
		pq.pop();
		cout << top << " ";

		for (int i = 0; i < adj[top].size(); i++) {
			int next = adj[top][i];
			degree[next]--;

			if (degree[next] == 0) {
				pq.push(-next);
			}
		}
	}

pq에 음수로 넣는 이유는 오름차순 정렬을 위해서이다.