백준 20303번: 할로윈의 양아치

백준 20303번: 할로윈의 양아치

import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())
candy = [0]+list(map(int,input().split()))
parent= [i for i in range(N+1)]
friends = [1 for _ in range(N+1)]

def find_parent(x):
    if parent[x]!=x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_find(a,b):
    a = find_parent(a)
    b = find_parent(b)
    if a<b:
        a,b = b,a
    parent[a] = b
    
for _ in range(M):
    a,b = map(int,input().split())
    union_find(a,b)
    
for i in range(1,N+1):
    if i!=parent[i]:
        friends[find_parent(i)] += 1
        candy[find_parent(i)] += candy[i]

parents = [i for i in set(parent)]
parent_num = len(parents)
dp=[[0 for _ in range(K)] for _ in range(parent_num)]
for i in range(1,parent_num):
    for j in range(K):
        x = parents[i]
        if(j<friends[x]):
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-friends[x]]+candy[x], dp[i-1][j])

print(dp[-1][-1])

knapsack으로 풀었더니 계속 시간초과가 나서, 질문 게시판을 참고해보니 유니온파인드를 써야한다는 힌트를 찾을 수 있었다. 그리고 한참을 했는데 아무리 해도 안됐다.. 계속 1%에서 틀렸다. 결국 다른 분들의 답을 찾았는데 로직은 똑같았다. 도대체 뭐가 문제인지 몇 시간동안 고민을 했는데 알고보니 friends, candy값을 갱신해주는 부분에서 find_parent(i)가 아니라 parent[i]로 하는 바람에 틀린거였다. find_parent(i)로 바꾸고 나니 바로 통과하길래 좀 허탈했다....

해당 문제에서는 유니온 파인드를 사용하기 위해 parent 배열을 스스로의 숫자로 초기화해주고, 아이들간의 관계가 들어올 때 갱신해준다. 하지만 만약에 (2,3) (1,2)의 순서로 입력값이 들어온다고 치자. 3의 부모가 2고, 2의 부모가 1이므로 parent[3]도 2여야한다. 하지만 입력값이 들어온 직후 parent[3]을 확인하면 2로 나온다. 3의 부모인 2가 parent[3]을 저장한 이후에 새롭게 갱신됐기 때문이다. 이러한 이유로 parent[i]로 바로 값을 찾아주려면 모든 관계를 입력한 후에 최소 한 번은 순회를 돌아줘야한다. (모든 관계가 입력된 경우라면, 위와같이 갱신되지 않은 경우를 대비하여 한 번만 전체 배열에 대해 순회를 돌아 find_parent(i)를 호출해주면 될 것이다.)

이번 문제를 계기로 유니온파인드랑 knapsack은 진짜 한동안 절대 안 잊어버릴 것 같다..............