백준 15586 : MooTube (Gold) (Python)

본문 링크

"""
존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.
"""
import sys,copy
input=sys.stdin.readline
from collections import deque

def Find(x): # 유니온 파인드의 Find 함수
    if x!=disjoint[x]:
        disjoint[x] = Find(disjoint[x])
    return disjoint[x]

def Union(a,b): # 유니온 파인드의 Union 함수
    a=Find(a) ; b=Find(b)

    if a==b:
        return
    if a>b:
        disjoint[a]=b
        dp[b]+=dp[a]
    else:
        disjoint[b]=a
        dp[a]+=dp[b]

N,Q=map(int,input().split())

graph=[] # 트리를 저장할 그래프를 선언한다.
dp=[1]*(N+1)

for i in range(N-1):
    a,b,c=map(int,input().split())
    graph.append((a,b,c))

graph.sort(key=lambda x:-x[2])
graph=deque(graph)
L=[ list(map(int,input().split())) for _ in range(Q) ] # 쿼리를 입력받는다.
Query=copy.deepcopy(L) # 쿼리를 미리 복사한다.

L.sort(key=lambda x:-x[0]) # k 값이 높은 순서대로 정렬한다.
disjoint=[ i for i in range(N+1) ] # 분리집합을 위한 배열을 만든다.

D={} # 오프라인 쿼리를 위한 딕셔너리
for K,V in L: # 쿼리 실행.
    while graph and graph[0][2]>=K:
        if Find(graph[0][0])!=Find(graph[0][1]):
            Union(graph[0][0] , graph[0][1])
            graph.popleft()
    D[(K,V)] = dp[Find(V)]-1

for K,V in Query: # 이전의 복사해둔 쿼리를 사용한다.
    print(D[(K,V)]) # 그때의 딕셔너리 값을 출력한다.

✅ 어떻게 풀것인가?

유니온파인드와 오프라인 쿼리를 사용했습니다.

먼저 그래프를 입력받은후 가중치에 대해 내림차순 으로 정렬해줍니다.
쿼리 또한 $K$ 값에 따라 내림차순 으로 정렬해줍니다.
그리고 정렬하기 전에 쿼리를 미리 Query 배열에 복사해줍니다.

disjoint 배열을 통해 분리집합을 구할 배열을 만들어 줍니다.

for K,V in L:

이후 정렬된 쿼리를 실행하고

while graph and graph[0][2]>=K:

그래프에 간선이 존재하면서 간선의 가중치가 $K$ 이상일때까지

if Find(graph[0][0])!=Find(graph[0][1]):

또한 두 집합이 분리되어있다면

Union(graph[0][0] , graph[0][1])
graph.popleft()

두 원소를 유니온 해주고 그래프의 원소를 삭제해줍니다.

즉 오프라인 쿼리를 통해서 처음에 아무런 간선이 연결되어있지 않다고 생각하고

정렬된 $K$ 이상의 쿼리에 한해서 노드 $V$ 를 다른 집합과 연결시킵니다.
이때 노드 $V$ 와 연결할수있는 간선이 $K$ 보다 작으면 $K$ 값을 감소시켜서 계속 연결해주는 겁니다. 내림차순으로 정렬하였으니깐요.

D[(K,V)] = dp[Find(V)]-1

이후 딕셔너리에 dp[Find(V)]-1 값을 넣어줍니다. -1 은 자기자신을 제외해야하기 때문입니다.

dp=[1]*(N+1) # 1 은 자기자신
def Union(a,b): # 유니온 파인드의 Union 함수
    a=Find(a) ; b=Find(b)

    if a==b:
        return
    if a>b:
        disjoint[a]=b
        dp[b]+=dp[a]
    else:
        disjoint[b]=a
        dp[a]+=dp[b]

개인적으로 가장 중요하다고 보는 유니온 부분입니다.
두 집합을 합칠때 dp 배열에 합치려는 집합의 크기를 더해줍니다.
처음에 생각없이 1 을 더했다가 맞왜틀을 엄청했습니다..

for K,V in Query: # 이전의 복사해둔 쿼리를 사용한다.
    print(D[(K,V)]) # 그때의 딕셔너리 값을 출력한다.

이후 이전에 복사해둔 입력의 쿼리에 대해서 딕셔너리 값을 출력하면됩니다.

✅ 중요한 부분

• 오프라인 쿼리를 통해 입력을 어떻게 유리하기 받을것인가?
• 두 집합을 합치는 테크닉에서 크기를 어떻게 더할것인가?