[백준OJ] 15591번 MooTube (Silver)

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

15591번: MooTube (Silver)

---

 

-풀이-

1. N-1개의 p , q , r 을 입력받아 tree를 만들어 준다.

2. Q개의 K와 V를 입력받아, 각각 DFS를 실행시켜주어 값을 도출한다.

 

DFS는 현재 정점의 USADO값이, K값보다 크거나 같으면 result값을 1 증가시킨 뒤, 자신과 연결된 다음 정점들도 dfs를 실행한 결과들을 모두 더해준 뒤 반환해준다. 재귀함수를 호출할 때, USADO의 값은, 현재 정점에서의 USADO의 값과, 다음 정점으로 갈때의 USADO의 값을 비교하여 더 작은 값을 넘겨주면 된다.

 

-시간복잡도-

질문 Q개 각각 DFS를 실행시켜주어야 하므로, O(QN) 이 된다.

 

-코드-

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

vector<pair<int,int>> maze[5000];
int n, q, k, v;

int dfs(int now, int parent, int usado,int k) {
	int result = 0;
	//시작점은 카운트 하지 않는다.
	if (parent!=-1&&usado >= k) {
		result++;
	}

	for (auto i : maze[now]) {
		int next = i.first;
		int next_cost = i.second;
		if (next != parent) {
			//재귀함수를 통해 result값을 업데이트 해준다.
			result += dfs(next, now, min(usado, next_cost), k);
		}
	}
	return result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		maze[a].push_back({ b,c });
		maze[b].push_back({ a,c });
	}

	for (int i = 0; i < q; i++) {
		cin >> k >> v;
		cout << dfs(v, -1, INT_MAX, k)<<"\n";
	}
}