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

문제풀이: www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

전형적인 비트마스킹(up-down) 문제입니다.

 

재귀함수를 사용하되, 배열에 방문값들을 저장하는 형태로 풀어나가면 됩니다! 

 

 

아래는 정답코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n = 0, m = 0;
vector <int> vec[1001];
int dp[1001] = {0, };

int solved(int num) {
	if (vec[num].size() == 0)
		return 1;
	int& ret = dp[num];
	if (ret != 0) return ret;

	ret = 1;
	for (int i = 0; i < vec[num].size(); i++) {
		ret = max(ret, solved(vec[num][i]) + 1);
	}

	return ret;
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t2].push_back(t1);
	}

	for (int i = 1; i <= n; i++) {
		cout << solved(i) << ' ';
	}
	cout << endl;
}