백준 - 15591 [C++]

 이 문제는 bfs로 푸는 문제이다. 처음에 이 문제를 풀때 순간 플로이드 워셜이 떠올라서 그렇게 풀어봤는데 애초에 값이 제대로 안 나왔다. 그래서 bfs로 다시 방향을 고치고 풀었는데, 이번에는 시간 초과가 났다. 처음에 bfs를 짤때는 start와 end를 두어 모든 짝에 대한 USADO를 저장했는데, 이런 식으로는 5000 * 5000 * 5000의 연산이 필요하게 되어 시간 초과가 난다. 다시 생각해보니 그럴 필요가 전혀 없었고, 시작점에서 출발하여 정점들을 방문하면서 USADO를 측정하고, 그 값이 k보다 크거나 같으면 카운트하면 되는 문제였다.

 문제를 풀 때 알고리즘을 안 보고 푸는 연습을 꼭 해야할 것 같다. 실제 코딩 테스트 시에는 이 문제가 어떤 알고리즘의 문제인지 알려주지 않기 때문이다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

vector<pair<int, int>> edges[5001];

#define INF	1000000001

vector<bool> visited;

int bfs(int start, int N, int k)
{
	visited = vector<bool>(N + 1, false);

	visited[start] = true;
	queue<pair<int, int>> q;
	q.push({ start, INF });

	int answer = 0;

	while (!q.empty())
	{
		pair<int, int> present = q.front();
		q.pop();

		for (int i = 0; i < edges[present.first].size(); i++)
		{
			pair<int, int> next = edges[present.first][i];

			if (!visited[next.first])
			{
				if (min(present.second, next.second) >= k)
				{
					answer++;
				}
				q.push({ next.first, min(present.second, next.second) });
				visited[next.first] = true;
			}
		}
	}

	return answer;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, Q;

	cin >> N >> Q;

	for (int i = 0; i < N - 1; i++)
	{
		int p, q, r;

		cin >> p >> q >> r;

		edges[p].push_back({ q, r });
		edges[q].push_back({ p, r });
	}

	for (int i = 0; i < Q; i++)
	{
		int k, v;

		cin >> k >> v;

		int cnt = bfs(v, N, k);
		
		cout << cnt << '\n';
	}

	return 0;
}