[BOJ]15591번: MooTube (Silver)

www.acmicpc.net/problem/15591

---

류트님 풀이(ryute.tistory.com/30)를 참고하여 해결하였습니다.

 

N,Q 제한이 5000으로 작은 편입니다.

때문에 하나의 쿼리를 O(N)에 해결해도 O(QN)에 해결가능합니다.

 

O(N)에 해결할 수 있는 방법은 하나의 쿼리당 BFS를 한 번 돌리면 됩니다.

주어진 동영상 v에 대해서 인접한 정점을 방문하면서 간선 가중치가 k이상인 정점만 방문합니다.

그러면 동영상 v와 연결되어있으면서 가중치가 k미만(== 유사도 k미만)인 정점은 제외됩니다.  

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ15591.cc