백준 Gold V. MooTube (Silver)

1. 풀이 시간

• 54분 12초

2. 난이도

• 유형: BFS, DFS
• 풀이법: ⬜ 15분 이내 ✅ 15분 이상
• 구현: ⬜ 30분 이내 ✅ 30분 이상
• 총평: ⬜ Easy ✅ Normal ⬜ Hard ⬜ Hell

3. 문제 설명

• N개의 동영상이 있다. 이 동영상들은 두 동영상 간의 연관도를 나타내는 'USADO'라는 관계로 연결되어 있다. 이 관계는 총 N-1개이며 각 동영상을 정점으로 하였을 때, A정점에서 B정점으로 가는 길(USADO)은 단 하나이다. 두 동영상 간의 최종 USADO는 두 동영상을 연결하는 USADO 값 중 최솟값이 된다. 이러한 규칙을 적용할 때 Q개의 질문에 답하여라. 각 질문에는 K와 i가 포함되어 있으면 다음과 같은 의미를 갖는다.
  • i번째 동영상과의 USADO가 K이상인 동영상의 개수를 구하여라.

4. 접근 방법

• 사용 알고리즘: BFS
• 각 동영상은 정점이 되고 지문에서 설명한 USADO는 정점을 잇는 간선이 되며 값이 가중치가 된다. 두 정점이 있을 때 각 정점으로 가는 길은 하나이며 이때의 최소 비용은 지나가는 간선의 가중치 값 중 최솟값이 되는 것이다. 또한, Q개의 질문에 답하기 위해서는 각 정점으로부터 다른 정점으로 가는 최소 비용을 미리 계산해놓아야 빠르게 답을 구할 수 있다. 이 값을 구하기 위해 1번 정점부터 N번 정점까지 BFS를 활용하여 각 정점으로의 최소 비용을 저장하는 2차원 배열을 구한 뒤, Q개의 질문에 대한 답을 구하여 해결하였다.

5. 배운 점 / 느낀 점

• 메모리 제한이 512MB로 넉넉하였고 각 조건이 1 ≤ N ≤ 5,000, 1 ≤ Q ≤ 5,000로 크지 않았기에 쉽게 풀 수 있는 문제였다.

문제 링크
My Solution Code