[백준 / BOJ] 15591 MooTube (Silver)

문제

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

15591번: MooTube (Silver)

농부 존은 MooTube라는 동영상 공유 서비스를 만들었다.

 

MooTube의 동영상들은 트리구조로 연결되어있고, 동영상 Vi를 볼때, Vi와 연결된 모든 동영상들중에 유사도가 Ki이상인 동영상들을 추천해준다. 이때, 동영상 Vi와 다른 동영상 Vj의 유사도는 Vi와 Vj 를 연결하는 경로의 최소 유사도이다.

 

소가 Vi동영상을 시청하고있을때, 유사도가 Ki이상인 동영상들의 갯수를 출력하는 문제다.

풀이

그래프 탐색문제였다.

처음엔 문제를 잘못이해하고 유사도가 Ki이하인 동영상들을 찾는거라 생각했는데, Ki이상인 동영상들을 찾는문제였다.

 

우선 이 문제를 완전탐색으로 풀수있는 이유는, 동영상 a와 동영상 b를 연결하는 유사도는 해당 거리의 최소유사도이므로 탐색중 Ki미만인 유사도가 나오면 탐색을 종료하면 되기 때문이다. 즉, 쿼리마다 최대 반복횟수는 O(N)이 된다.

 

구현은 간단한데, 입력받은 동영상을 기준으로 탐색을하다, 유사도가 w미만인 지점을 만나면 해당 경로로는 탐색을 종료하면된다.(이후에 만나는 동영상들은 모두 유사도가 w미만이 된다.)

 

그래프가 트리구조이기때문에, 연결되어있지 않은 동영상은 없다.

 

쿼리마다 N번 반복으로 모든 동영상을 찾으며, K번 쿼리가 주어지므로 시간복잡도는 O(NK)가 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/MooTube%20(Silver)/main.cpp

devxb/JJUNalgo