[Python] 15991. MooTube (Silver)

문제

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

15591번: MooTube (Silver)

 

---

풀이 과정

동영상과 유사도를 가지고 그래프를 만들어
농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 

따라서 이어진 동영상의 유사도가 k이상이면 해당 동영상에서 또 이어진 동영상을 탐색해야 하는 과정을 반복해야 하고, 동영상 개수를 세야 하므로 BFS를 활용하였다. 

여기서 주의할 점은 존은 두 쌍 사이의 동영상의 유사도를 그 경로의 모든 연결들의 유사도 중 최솟값으로 하기로 했으므로,
유사도를 최솟값으로 갱신하는 코드가 들어가야 한다. (근데 안 넣어도 통과했음)

따라서

1. 입력받은 비디오 쌍과 유사도를 가지고 양방향 인접 리스트 만들기 
2. 동영상 v에서 유사도 k이상의 동영상이 몇 개 인지 묻는 농부 존의 q개 질문을 받는다.
3. BFS로 들어가 큐에 시작 비디오와 초기 유사도를 넣어준다.
   (초기 유사도는 나중에 최솟값으로 갱신돼야 하므로 큰 값으로 잡아준다.)
   
   3-1큐에서 현재 비디오와 최소 유사도를 가져온다.
   3-2. 현재 비디오에서 이어진 비디오들을 탐색한다. 
   3-3. 다음 비디오로 이어진 유사도가 더 작은 값이라면 갱신시켜준다.
   3-4. 다음 비디오가 방문하지 않은 곳이고, 유사도가 k 이상이라면,
            해당 비디오에서 이어진 비디오를 탐색해야 하므로 큐에 넣고 개수를 +1 해준다. 
   3-5. 3-1 ~ 3.4 과정을 큐가 빌 때까지 해준다. 
   3-6. 큐가 비면 동영상 개수를 return 해준다. 

 

---

코드

from collections import deque

# 유사도 k 이상의 비디오 몇개인지 판별하기
def bfs(k, v):
    visited = [0 for _ in range(n+1)]
    visited[v] = True
    queue = deque([(v, 999999999999999)])
    cnt = 0
    while queue:
        now, usado = queue.popleft()    # 현재 비디오, 최소 유사도

        for nxt_v, nxt_u in graph[now]:
            # 존은 두 쌍 사이의 동영상의 유사도를 그 경로의 모든 연결들의 유사도 중 최솟값으로 하기로 함
            # 따라서 현재까지의 최소 유사도와 현재 비디오와 다음 비디오의 유사도 중 최솟값으로 갱신
            nxt_u = min(usado, nxt_u)
            # 방문하지 않은 곳이고, 유사도가 k이상이라면
            if not visited[nxt_v] and k <= nxt_u:
                queue.append((nxt_v, nxt_u))
                cnt += 1
                visited[nxt_v] = True
    return cnt


n, q = map(int, input().split())
# 동영상 인접 리스트 만들기
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    v1, v2, usado = map(int, input().split())
    graph[v1].append((v2, usado))
    graph[v2].append((v1, usado))

# 농부 존의 q개 질문
for _ in range(q):
    k, v = map(int, input().split())
    print(bfs(k, v))