백준 1766 문제집

A, B가 들어오면

A->B 의 edge를 만들고

완성된 그래프에 대해 위상정렬을 수행하는 문제.

단 위상정렬을 할 때 

위상정렬큐에 indegree(진입차수)가 0인 노드를 한번에 다 넣지 말고 한번에 하나씩만 넣어야 한다.

풀이하자면 다음과 같다

#

indegree가 0인 노드를 하나만 찾아서 그것 하나만 큐에 넣는다(다른 것과 다르게 모두 넣지 않는다.).

큐에서 하나를 빼고 그 노드의 진입차수를 1뺀다(-1로 만들어주어 다음 계산시에 영향을 끼치지 않게 한다.).

그 노드와 연관된 vertex들의 indegree를 1 뺀다.

다시 루프 처음으로 돌아간다.

#

이런 식으로 하면 큐에 가장 적은 숫자부터 들어가니 낮은 번호부터 나오게 되어 문제의 조건3을 만족한다.

그런데 이 알고리즘대로 수행하면 큐가 필요 없다. 

항상 큐에 하나의 노드만 들어가는데, 그 노드만 저장하고 있으면 문제 없다.

아, 추가로 큐가 비어있는지 확인해야 하는데, (큐가 비어있다 == 노드를 저장하지 못했다) 니까 노드를 저장하는 변수(now)가 변하였는지 확인하면 된다.

따라서 아래와 같은 코드가 나온다.

사실, 코드를 짤때는 시간초과가 나올줄 알았는데 약 300ms로 통과했다.

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS

#include <iostream> 
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>

using namespace std;

int N, M;
int indegree[32002];
vector<int> adj[32002];

int main() {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {
		int from, to;
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		indegree[to]++;
	}
	
	int now;

	while (true) {
		now = -1;
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) {
				now = i;
				break;
			}
		}
		if (now == -1) break;
		indegree[now]--;
		printf("%d ", now);

		for (int next : adj[now]) {
			indegree[next]--;
		}
	}

	return 0;
}

그런데 뭔가 수행시간이 다른 사람들에 비해 길다는걸 느꼈다.

최적화를 더 할수 있나~ 싶었는데, 아차, 우선순위 큐를 쓰면 되겠다 싶었다.

그러니까 위상정렬큐를 우선순위큐로 구현하고, indegree가 0인 노드를 죄다 전부 우선순위큐에 넣은 뒤에,

루프에서 노드를 하나씩 뺄때는 우선순위큐의 최소숫자를 빼면 되겠다 싶었다.

그렇게 되면 indegree가 0인 것중 항상 최소 숫자를 가진 노드(즉, 가장 쉬운 문제)부터 풀게 되니까 조건 3에 부합하게된다.

따라서 아래와 같은 코드로 68ms로 시간을 줄였다.

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS

#include <iostream> 
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>
#include <functional>

using namespace std;

int N, M;
int indegree[32002];
vector<int> adj[32002];
priority_queue<int, vector<int>, greater<int>> topoloPQ;

int main() {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {
		int from, to;
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		indegree[to]++;
	}

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

	while (!topoloPQ.empty()) {
		int now = topoloPQ.top();
		topoloPQ.pop();
		indegree[now]--;
		printf("%d ", now);

		for (int next : adj[now]) {
			indegree[next]--;
			if (indegree[next] == 0) {
				topoloPQ.push(next);
			}
		}
	}

	return 0;
}