백준 17250 : 은하철도 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])

    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a>b:
        disjoint[a]=b
        dp[b]+=dp[a]
    elif a<b: #똑같은 경로는 더하면 안됨.
        disjoint[b]=a
        dp[a]+=dp[b]

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

disjoint=[0]*(N+1)

for i in range(1,N+1):
    disjoint[i]=i

dp=[0]*(N+1)

for i in range(N):
    dp[i+1]=int(input())


for i in range(M):

    a,b=map(int,input().split())
    Union(a,b)
    print(dp[min(Find(a),Find(b))])

📌 어떻게 접근할 것인가?

유니온 파인드를 구현해주면 되는 문제입니다.

다만 문제에서 두 지점의 경로를 주어졌을때 바로 값을 출력해야합니다.

이는 $a$,$b$ 를 $Union$ 한 후에 print(dp[min(Find(a),Find(b))]) 를 사용하면 답을 출력할 수 있습니다.

또한 주의해야할 점은 같은 경로는 더해주면 안됩니다.