BOJ 16562 친구비(Python 3)

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

유니온 파인드를 공부하다가 정리할 필요가 있어서 글을 쓰게 되었다.

내 풀이 방법은 v,w의 값을 입력 받을 때

v의 친구비가 더 높으면 v의 루트를 w의 루트로 해두고, w의 친구비가 더 높으면 w의 루트를 v의 루트로 해두었다.

이렇게 해두면 1차적으로 값들이 끼리끼리 모이게 되고, 이 상태에서 for문을 이용해 각 학생의 루트를 다시 구해준다.

이러면 어떤 학생한테 돈을 줘야하는지 알 수 있으니 ans에 값을 더하면 된다.

코드 확인

def Find(x):
    if x==P[x]:return x
    P[x]=f(P[x])
    return P[x]
n,m,k=map(int,input().split())
A=[0]+[*map(int,input().split())]
P=[i for i in range(n+1)]
V=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    x=Find(a)
    y=Find(b)
    if A[x]>A[y]: P[x]=y
    else: P[y]=x
# print(P)
for i in range(1,n+1):
    P[i]=Find(i)
# print(P)
ans=0
for i in range(1,n+1):
    x=P[i]
    if V[x]==0:
        V[x]=1
        ans+=A[x]
print(['Oh no',ans][ans<=k])

-------------------------------------------------------------------------

틀린 부분 찾는데 쓰인 반례

5 4 100

1 2 3 4 5

1 5

4 2

2 3

4 5

답:1

10 9 1000

1 2 3 4 5 6 7 8 9 10

1 2

3 4

5 6

7 8

9 10

7 9

6 4

2 8

5 1

답 1

값을 넣어도 전부 제대로 구할 수 있는 코드인지 의심스러웠는데 생각해보면

- 연합끼리 일단 뭉쳐있게 구현함

- 무조건 값이 적은 곳으로 뿌리를 저장해두었다.

- for문을 돌려서 각 학생의 뿌리를 그 학생이 속한 연합중에 값이 제일 작은 학생으로 저장해둔다.

이므로 최솟값이 나올 수 밖에 없는 코드인 것 같다.