boj, 백준) 15591. MooTube (Silver) (C/C++)

1. 문제 링크

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

15591번: MooTube (Silver)

 

2. 문제 개요

N개의 동영상이 있고 동영상간 유사도(USADO) N-1개를 측정했다. 동영상 A, B의 사이의 유사도의 최솟값이 주어진 K보다 크다면 동영상은 추천된다. Q개의 질문에 대해 위의 조건을 만족하는 동영상의 개수를 답하시오.

 

3. 문제 힌트

동영상 A, B사이의 모든 유사도를 측정해 보아야 한다.

A에서 출발해서 이때까지의 유사도의 최솟값을 갖고 가면서 최솟값을 찾아보자..

 

4. 문제 풀이

시간복잡도는 O(QN)이다.

왜냐하면 Q개의 질문에 대해서 BFS(N)을 해야 하기 때문.

 

동영상 A에서 출발해서 그래프내의 모든 정점을 살펴봐야 한다.

가는 도중에 K보다 USADO가 작다면 그 뒤의 동영상들은 살펴볼 필요가 없다. 이런 걸 가지치기해주는 방식으로 시간을 줄일 수 있다.

하지만 시간복잡도는 여전히 O(QN)이라는 점! 데이터 케이스에 따라 시간이 천차만별로 나오겠다.

 

그래서 일단 모두 찾아보는 방식, 가지치기하는 방식으로 구현해보았고 약 700ms, 약 300ms로 시간은 많이 단축시킬 수 있었다.

 

 

BFS를 할 때는

{이때까지의 최솟값 , 다음 정점}의 쌍으로 Queue에 넣어서 하면 된다. 

 

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

constexpr int MAX = 0x4fffffff;

struct EDGE{
	EDGE() {}
	EDGE(int to_, int r_) :to(to_), r(r_) {}
	int to, r;
};
struct ITEM
{
	ITEM() {}
	ITEM(int bef_, int v_ ) : bef(bef_), v(v_) {}
	int v, bef;
};

vector<vector<EDGE>> adj;

int n, q;

int main()
{
	scanf("%d %d", &n, &q);
	adj.resize(n + 1);

	for (int i = 0; i < n - 1; ++i){
		int from, to , r;
		scanf("%d %d %d", &from, &to, &r);
		
		adj[from].push_back(EDGE(to, r));
		adj[to].push_back(EDGE(from, r));
	}

	while (q--)
	{
		int k, v, ans = 0;
		scanf("%d %d", &k, &v);

		queue<ITEM> bfsQueue;

		vector<bool> visited(n + 1, false);

		visited[v] = true;
		bfsQueue.push(ITEM(MAX,v));

		while (!bfsQueue.empty())
		{
			ITEM cur = bfsQueue.front();
			bfsQueue.pop();

			for (EDGE item : adj[cur.v])
			{
				if (visited[item.to] == true)
					continue;

				int next = item.to;
				int r = item.r;

				int minval = min(cur.bef, r);

				if (k <= minval) {
					++ans;
					visited[next] = true;
					bfsQueue.push(ITEM(minval, next));
				}
				
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}

 

6. 결과