BOJ1516/ C++

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

1766번: 문제집

백준 온라인저지 1766번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

#include<iostream>
#include<queue>
#include<vector>
#define MAX 32001

using namespace std;

int num[MAX];
vector<int> v[MAX];
bool visited[MAX];
int N, M;

void Input() {
	int a, b;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		num[b]++;
	}
}

void solution() {
	int cnt = 0;


	while (cnt<N) {
		int current;
		
		for (int i = 1; i <= N; i++) {
			if (num[i] == 0 && !visited[i]) {	
				current = i;
				cout << i << " ";
				visited[i] = true;
				cnt++;
				break;
			}
	
		}
		for (int i = 0; i < v[current].size(); i++) {
			num[v[current][i]]--;
		}
	}
}

int main() {
	Input();
	solution();
}

아이디어

a번 문제를 b번문제보다 먼저푸는게 좋지만 가능하면 번호가 낮은 문제부터 푸는게 좋은 문제

위상정렬을 하되 번호가 낮은 순으로 출력해야함

q를 돌면서 진입차수를 지우고 매번 진입차수가 0이면서 풀지않은 문제를 번호가 낮은 순으로 출력함

단, 큐 1번에 1개만 출력해야함