백준 14567 - 선수과목 (Prerequisite)(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

위상 정렬을 이용하면 쉽게 풀 수 있는 문제였습니다.

어떤 과목을 듣기 위해서 먼저 들어야 하는 과목의 조합이 M개가 주어질 떄
N개의 과목은 각각 몇 번째 학기에 이수 가능한지 구하는 문제입니다.
-> 어떤 정점을 가기 위해서 먼저 방문해야하는 정점이 있으면 위상 정렬 알고리즘을 사용하면 편합니다.

나중에 이수가 가능한 과목이 주어지면 해당 과목의 값을 1씩 증가해줍니다.
그렇다면, 1학기에 바로 이수가 가능한 과목들은 전부 값이 0이 되있을 것입니다.
-> 값이 1인 과목이 있다?
-> 해당 과목은 2학기에 바로 수강이 가능한 과목들입니다.

이런 식으로 주어진 과목의 관계를 통해서 순차적으로 확인해, 몇 학기에 수강이 가능한지를 찾아주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int N, M;
vector<vector<int>> connect;
int step[1001];
int subject[1001];
queue<int> q;


void topological_sort(){
	for(int i = 1; i <= N; i++){
		if(step[i] == 0){
			q.push(i);
			subject[i] = 1;
		}
	}
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(auto &next : connect[x]){
			step[next]--;
			subject[next] = max(subject[next], subject[x] + 1);
			if(step[next] == 0) q.push(next);
		}
	}
}

void solve(){
	topological_sort();
	for(int i = 1; i <= N; i++) cout << subject[i] << " ";
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	connect.resize(N+1, vector<int>());
	for(int i = 1; i <= M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		connect[x].push_back(y);
		step[y]++;		
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.