[GOLD 5] MooTube

1. 문제 링크

Gold 5 MooTube

15591번: MooTube (Silver)

---

 

2. 문제 이해 및 풀이 전략

 

소에게 유튜브를 보여준다고 모든 영상에 영상끼리 USADO( 유사도?! )를 설정, 처음 보기 시작한 영상(V1)부터 유사도가 있는 영상이 지정한 유사도(K1) 보다 높은 영상들의 수를 구하고 싶어한다.

 

처음 재생되는 영상의 번호를 시작점으로 유사도가 설정된 영상 전체는 검색해 제한값보다 높은 영상을 모두 체크하면 될 것 같다.

 

그래프로 대입했을 때, 「소는 정점 」 , 「 유사도는 정점끼리의 거리 」 , 「 유사도 설정은 거리 제한」 정도로 이해하면 되겠다.

---

3.  풀이 코드

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

using namespace std;

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); setvbuf(stdout, nullptr, _IOFBF,BUFSIZ)

int N, Q;
int p1, q1, r1;
bool visited[5001];

long BFS(long k1, long v1, const vector<vector<pair<int, int>>>& vec)
{
	long answer = 0;

	// 방문체크 초기화
	int size = vec.size();
	for (int i = 1; i <= size; i++)
		visited[i] = false;

	visited[v1] = true;

	queue<int> q;
	q.push(v1);

	while (q.empty() == false)
	{
		int current = q.front();
		q.pop();

		const int vecSize = vec[current].size();
		for(int i = 0; i < vecSize; i++)
		{
			int next = vec[current][i].first;
			int nextUSADO = vec[current][i].second;

			if(visited[next] == true) continue;
			if(nextUSADO < k1) continue;

			answer++;
			visited[next] = true;
			q.push(next);
		}
	}

	return answer;
}

int main()
{
	fastio;

	//  소의 수, 질문 수
	cin >> N >> Q;

	vector<vector<pair<int, int>>> USADO(N + 1);

	for(int i = 0; i < N - 1; i++)
	{
		cin >> p1 >> q1 >> r1;

		USADO[p1].push_back({q1, r1});
		USADO[q1].push_back({ p1, r1 });
	}

	int k1, v1;
	while (Q--)
	{
		cin >> k1 >> v1;

		cout << BFS(k1, v1, USADO) << "\n";
	}

	return 0;
}

---

4. 결과 및 회고

 

두번의 시간 초과는 BFS를 실행하기 위해 필요한 매개변수로 Vector 전체를 필요하게 작성했는데 실수로 참조 연산자를 빼먹어 복사 과정에서 굉장히 손해를 봤기 때문이다.

 

Call By Reference, Call By Value 다시한번 체크