굳건하게

문제 : https://www.acmicpc.net/problem/1516

위상 정렬

● 건물을 동시에 지을 수 있으므로, 각 건물별로 필요한 시간은 그래프 경로 중 가장 긴 경로가 된다.

● ans[i] := 건물 순서를 고려해 i 번 째 건물을 짓는데 필요한 최대 시간.

● time[i] := 단순히 i번 째 건물만 짓는데 걸리는 시간.

위상 정렬을 이용해 inDegree가 0인 노드부터 탐색을 시작해, 현재 탐색중인 노드에서 연결된 노드들의 ans[i] 를 계속 갱신을 해주면 된다. 예시를 통해 다뤄보겠다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, M, inDegree[501] = {}, time[501] = {}, ans[501] = {};
	vector<int> graph[501] = {};
	stack<int> s;

	cin >> N;
	for (int i = 1, x; i <= N; i++) {
		cin >> time[i];
		while(1){
			cin >> x;
			if (x == -1)
				break;
			graph[x].push_back(i);
			inDegree[i]++;
		}
	}

	for (int i = 1; i <= N; i++)
		if (inDegree[i] == 0){
			s.push(i);
			ans[i] = time[i];
		}

	while (!s.empty()) {
		int cur = s.top();
		s.pop();

		for (int i = 0; i < graph[cur].size(); i++) {
			inDegree[graph[cur][i]]--;
			ans[graph[cur][i]] = max(ans[graph[cur][i]], ans[cur] + time[graph[cur][i]]);
			if (inDegree[graph[cur][i]] == 0) {
				s.push(graph[cur][i]);
			}
		}
	}

	for (int i = 1; i <= N; i++)
		cout << ans[i] << '\n';

	return 0;
}

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

위상정렬 , 그래프이론

● 위상정렬 + 추가조건이 붙은 문제로 자료구조 우선순위 큐를 이용하면 쉽게 해결할 수 있습니다.

● 입력을 받아 x문제와 y문제가 선행 조건이 x가 먼저 풀려야되면 x에서 y로 가는 방향 간선을 그려주고

y의 inDegree 값을 증가시킵니다.

● inDegree가 0이라는 뜻은 먼저 풀려야되는 문제가 없다는 뜻으로 지금 당장 풀어도 됩니다. 하지만, 우리는 풀어도 되는 문제 중 난이도가 작은(문제 번호가 작은) 문제를 먼저 풀어야되므로, 가장 작은 값에 우선 순위를 부여하는 우선순위 큐를 만들어 활용하면 됩니다.

● inDegree가 0인 문제들을 모두 우선순위 큐에 넣고 하나씩 뽑아가며(가장 번호가 작은 문제) 출력하고, 해당 문제랑 연결되어 있는 문제들의 inDegree 값을 갱신해줍니다. 다시 inDegree가 0이 되는 문제들을 우선순위 큐에 넣어가며 모든 문제들을 출력하면 됩니다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, M, inDegree[32001] = {};
	vector<int> graph[32001] = {};
	priority_queue<int, vector<int>, greater<int>> pq;

	cin >> N >> M;
	for (int i = 0, x, y; i < M; i++) {
		cin >> x >> y;
		graph[x].push_back(y);
		inDegree[y]++;
	}
	for (int i = 1; i <= N; i++)
		if (inDegree[i] == 0)
			pq.push(i);

	while (!pq.empty()) {
		int cur = pq.top();
		pq.pop();
		for (int i = 0; i < graph[cur].size(); i++) {
			inDegree[graph[cur][i]]--;
			if (inDegree[graph[cur][i]] == 0)
				pq.push(graph[cur][i]);
		}
		cout << cur << ' ';
	}

	return 0;
}

문제 : https://www.acmicpc.net/problem/15666

[ 알고리즘풀이 ]

 중복해서 숫자를 사용할 수 있으므로, 사용할 수 있는 숫자들만 따로 check해 list를 오름차순으로 만들고 Backtracking 기법을 이용해 M개의 숫자를 뽑는데, 가장 마지막에 뽑은 숫자도 같이 매개변수로 넘겨주면서 그 값보다 크거나 같은 값들만 뽑는다.

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

int N, M;
bool check[10001];
vector<int> list;

void BT(vector<int> v, int start) {
	if (v.size() == M) {
		for (int i = 0; i < M; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 0; i < list.size(); i++) {
		if(start <= list[i]){
			v.push_back(list[i]);
			BT(v, list[i]);
			v.pop_back();
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M;
	for (int i = 0, x; i < N; i++) {
		cin >> x;
		check[x] = 1;
	}
	for (int i = 0; i < 10001; i++)
		if (check[i])
			list.push_back(i);

	sort(list.begin(), list.end());

	vector<int> v;
	BT(v, 0);

	return 0;
}

문제 : https://www.acmicpc.net/problem/2252

[ 알고리즘풀이 ]

 전형적인 위상 정렬 문제입니다.

 입력에 맞춰 graph를 그리고, 노드마다 inDegree 값을 구해 inDegree가 0인 노드부터 시작해 해당 노드와 연결된 노드들의 inDegree 값을 깎아가며 inDegree가 0이 된 노드들을 추가로 탐색해나가면 됩니다.

#include<iostream>
#include<vector>
#include<stack>

using namespace std;
int N, M, inDegree[32001];
vector<int> list[32001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0, x, y; i < M; i++) {
		cin >> x >> y;
		list[x].push_back(y);
		inDegree[y]++;
	}
	stack<int> s;
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0)
			s.push(i);
	}

	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		cout << cur << ' ';
		for (int i = 0; i < list[cur].size(); i++) {
			inDegree[list[cur][i]]--;
			if (inDegree[list[cur][i]] == 0)
				s.push(list[cur][i]);
		}
	}

	return 0;
}