글 읽기 - 유니언 파인드, 분리 집합에 대한 질문입니다

injoon2018 3년 전 0

https://www.acmicpc.net/problem/16562 문제를 풀다가 생긴 궁금증입니다.

예를들어서 1번부터 5번까지 학생이 있고

이런식으로 유니언 해 나간다면

[0, 1, 2, 3, 4, 1]
[0, 1, 2, 3, 2, 1]
[0, 1, 2, 2, 2, 1]
[0, 1, 1, 2, 2, 1]

이런 흐름으로 유니언될 것입니다.

그런데 마지막에 2번은 루트인데 그걸 1번 집합과 유니언 해버리면 2번 밑에 것들도 다 1번으로 바뀌어야할텐데

그걸 효율적으로 하는 방법이 있을까요? 어느 블로그에서 자동으로 된다고 하던데 안되어서

주석처리한 부분을 제가 직접 넣었습니다. 하지만 저렇게하면 O(N)이 될 것 같아서 다른 방법이 있나 여쭤봅니다

import sys
import math

def getParent(v):
    if zip[v]==v:
        return v
    else:
        y = getParent(zip[v])
        zip[v] = y
    return zip[v]

def unionParent(a, b):
    a = getParent(a)
    b = getParent(b)
    if a < b:
        # for i in range(1, N+1):
        #     if zip[i]==b:
        #         zip[i] = a
        zip[b] = a
    else:
        # for i in range(1, N+1):
        #     if zip[i]==a:
        #         zip[i] = b
        zip[a] = b

def findParent(a, b):
    if getParent(a)==getParent(b):
        return True
    else:
        return False

N, M, K = map(int, input().split())
zip = [i for i in range(N+1)]
price = [0]+list(map(int, input().split()))

for _ in range(M):
    v, w = map(int, input().split())
    unionParent(v, w)
    print(zip)
prices_per_groups = [sys.maxsize for i in range(N+1)]

for i in range(1, N+1):
    prices_per_groups[zip[i]] = min(prices_per_groups[zip[i]], price[i])

ans= 0
for i in range(1, N+1):
    if prices_per_groups[i] != sys.maxsize:
        ans += prices_per_groups[i]

if ans <=K:
    print(ans)
else:
    print("Oh no")

shg9411 3년 전 1

getParent 함수 내에서 하고계십니다.

경로 압축(path compression)

else:
    zip[v] = getParent(zip[v])
    return y

injoon2018 3년 전 0

@shg9411 댓글감사합니다!

그런데

5 4 100

1 2 3 4 5

1 5

4 2

2 3

4 5

이 데이터를 입력하고 unionParent를 할때마다 zip을 출력해보니 맨 마지막 단계에서 안되더라고요

만약 다 합쳐졌으면 맨 마지막에 zip이 전부 1이어야할텐데..

injoon2018 3년 전 0

@shg9411 말씀하신 경로압축은 혹시 리프에서 루트로 타고 올라갈때 바뀌는 것 아닌가요? 만약 루트 자체가 다른 집합에 붙어버리면 루트 밑의 노드들은 안바뀌는 것 아닌가요?

sait2000 3년 전 0

안 바뀝니다. 하지만 함수를 여러번 호출하면 나중에 호출하는 경우에 완전히 루트에 붙어있지 않아도 위쪽 경로가 압축되어있어 적은 시간이 걸리기 때문에 평균적으로는 꽤 빠르게 동작합니다. 하지만 파이썬 같은 경우 기본 설정은 재귀 깊이에 제한이 있기 때문에 O(N)번의 재귀 함수 호출이 필요한 데이터에서 런타임에러가 나기도 합니다.

injoon2018 3년 전 0

@sait2000 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

유니언 파인드, 분리 집합에 대한 질문입니다

injoon2018 3년 전 0

shg9411 3년 전 1

injoon2018 3년 전 0

injoon2018 3년 전 0

sait2000 3년 전 0

injoon2018 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말