[C++]백준 15591번: MooTube(Silver)

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

15591번: MooTube (Silver)

 

1. 접근

"좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다." 에서 스패닝트리를 쓰는건가 생각해봤지만

 

그냥 기알고리즘 적용한다기보다 문제에 맞춰 로직을 짜면 됐다.

 

2. 풀이

스패닝트리 특징을 생각하며 로직을 짜긴했다.

모두 이어져있으니 USADO를 구할 때 Vi부터 뻗어져 나가는 정점을 하나씩 보면서 K보다 큰 정점 개수를 기록하면되는 것

 

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <climits>

using namespace std;

struct comp{
	bool operator() (pair<pair<int, int>, long long> a, pair<pair<int, int>, long long> b) {
		return a.second > b.second;
	}
};

int N, Q, p, q, r, k, v;

vector<pair<int, int>> e[5001];
int u[5001][5001] = { 0, };

int ans[5000] = { 0, };

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> Q;
	
	for (int i = 0; i < N - 1; i++) {
		cin >> p >> q >> r;
		e[p].push_back({ q,r });
		e[q].push_back({ p,r });

		u[p][q] = r;
		u[q][p] = r;
}

	for (int i = 0; i < Q; i++) {
		cin >> k >> v; // upper cost k from vertex v 

		int cnt = 0;
		bool chk[5001] = { false, };
		queue<pair<int, long long>> qu;
		qu.push({ v, LLONG_MAX });
		chk[v] = true;

		while (!qu.empty()) {
			int cv = qu.front().first;
			long long cu = qu.front().second;
			qu.pop();

			for (int j = 0; j < e[cv].size(); j++) {
				if (!chk[e[cv][j].first]) {
					int nv = e[cv][j].first;
					long long nu = cu > e[cv][j].second ? e[cv][j].second : cu;
					
					qu.push({ nv, nu });
					chk[nv] = true;
					
					if (nu >= k) {
						cnt++;
					}
				}
			}
		}

		ans[i] = cnt;
	}

	for (int i = 0; i < Q; i++)
		cout << ans[i] << "\n";

	return 0;
}