[백준] MooTube(Sliver) : 15591 Python (Pypy)

오랜만에 백준을 풀었고, 오랜만에 시간 초과 늪에 빠졌다. 최대한 시간을 줄여 파이썬까지 통과해보고 싶었지만 아직 내실력에서는 Pypy통과가 최선이었다.

문제를 간략히 설명하자면, 존이 N개의 동영상 중 N-1개의 동영상 쌍을 만들어서 유사도를 구해놓았다. 동영상 쌍을 만들 때 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 만들었을 때, Q개의 질문(v번의 동영상과 유사도가 k이상인 동영상의 개수)의 답을 구하는 문제이다.

문제에서 가장 큰 힌트부분은 한 동영상에서 한 동영상으로 가는 경로가 반드시 하나인 점. 즉, 방향이 존재하지 않고 사이클이 없는 그래프인 트리구조로 만들 수 있다는 점이다. 

나는 위 점에서 힌트를 얻어 딕셔너리를 활용하여 트리를 만들었고, 이를 이용한 BFS탐색을 해보았다.

완성된 나의 코드이다.

역시 시간초과가 나서 파이썬으로는 해결하지 못했는데, 그 이유 중 하나가 BFS에서 nice한 종료 조건을 만들어내지 못했기 때문에 그런 것 같다.

백준에서 시간초과를 해결하는 것은 너무 어려운 것 같다. 연습을 통한 숙달 후 이문제를 다시 파이썬으로 통과해봐야겠다. 

 

문제출처 : 백준 https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)