[백준] 15591 MooTube

백준 15591 MooTube

문제

농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다.

MooTube에서 농부 존의 소들은 재밌는 동영상을 서로 공유할 수 있다.

소들은 MooTube에 1부터 N까지 번호가 붙여진 N개의 동영상을 이미 올려 놓았다.

하지만 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.

존은 MooTube 동영상에 대해 연관 동영상 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성 있는 영상을 추천받을 수 있다.

존은 두 동영상이 서로 얼마나 가까운지 측정하는 단위인 USADO를 만들었다.

존은 N-1개의 동영상 쌍을 골라 직접 두 쌍의 USADO를 계산했다.

이후 존은 동양상들을 네트워크 구조로 바꿔 각 동영상을 정점으로 나타내기로 했다.

또한 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다.

존은 임의의 두쌍 사이 동영상의 유사도를 그 경로의 모든 연결들의 유사도 중 최솟값으로 하기로 했다.

존은 어떤 주어진 MooTube 동영상에 대해 값 K를 정해 그 동영상과 유사도가 K이상인 모든 동영상이 추천되도록 할 것이다.

하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것에 방해가 될까 걱정하고 있다.

따라서 그는 K를 적절한 값으로 결정하려한다.

농부 존은 어떤 K값에 대한 추천 동영상의 개수를 묻는 질문 여러개에 당신이 대답해 주기를 바란다.

입력

• 첫째줄: N, Q
• 2 ~ n: 동영상 쌍의 유사도 시작노드 p, 연결 노드 q, USADO r
• Q: 농부 존의 질문 Q
  • k, q: k = 유사도 q = 탐색할 노드

출력

Q개의 질문에 대한 답

힌트

1, 2번 동영상의 유사도: 3

2, 3번 동영상의 유사도: 2

2, 4번 동영상의 유사도: 4

• 1, 4번 동영상의 유사도: min(3, 4) = 3
• 1, 3번 동영상의 유사도: min(3, 2) = 2

K=1일때 2번 동영상, K=3일때 1번 동영상, K=4일 때 1번 동영상을 보면 각각 몇개의 동영상이 추천될 까 궁금해한다.

1. K=1인 경우
   • 2번 동영상에서 추천되는 영상: 1, 3, 4
2. K=4인 경우
   • 1번 동영상에서 추천되는 영상: X
3. K=3인 경우
   • 1번 동영상에서 추천되는 영상: 2, 4번 동영상

해결 방식

BFS를 통해 구현

과정

1-2: 3

2-3: 2

2-4: 4

[[ ], [(2, 3)], [(3, 2), (4, 4)]]

Q. k = 1, v = 2

1. q = [(2, inf)]
2. 리스트의 2번째 노드 조사: 2번 영상과 유사도가 1이상인 경우 카운트

   • n_v = 1, n_u = 3 조사

     → 2번, 1번 영상의 USADO = 3

     → q = [(1, 3)], result = 1

   • n_v = 3, n_u = 2

     → 2번, 3번 영상의 USADO = 2

     → q = [(1, 3), (3, 2)], result = 2

   • n_v = 4, n_u = 4

     → 2번, 4번 영상의 USADO = 4

     →q = [(1, 3), (3, 2), (4, 4)], result = 3

3. (1, 3) pop

   • n_v = 1, n_u = 2

     → q = [(3, 2), (4, 4)], result = 3 (이미 방문했던 노드이므로 pass)

   • pop (3, 2), pop (4, 4)도 동일

코드

from collections import deque
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
usados = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, usado = map(int, input().split())
    usados[a].append((b, usado))
    usados[b].append((a, usado))

# 연결된 노드들의 유사도 계산
for i in range(q):
    k, v = map(int, input().split())
    visited = [False] * (n+1)
    result = 0
    q = deque()
    q.append([v, float('inf')])
    visited[v] = True

    while q:
        v, usado = q.popleft()
        for n_v, n_u in usados[v]:
            n_u = min(usado, n_u)
            if n_u >= k and not visited[n_v]:
                result += 1
                q.append((n_v, n_u))
                visited[n_v] = 1
    print(result)