서로소 집합(Disjoint-sets)

서로소 집합?

: 서로 중복 원소가 없는 집합들. 다시 말해서 교집합이 없는 집합

 

집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.

 

 

 

 

상호 배타 집합 표현 - Tree

• 하나의 집합을 하나의 트리로 표현한다
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

 

 

 

상호 배타 집합에 대한 연산

• Make_Set(x) : 유일한 멤버 z를 포함하는 새로운 집합을 생성하는 연산
• Find_Set(x) : x를 포함하는 집합을 찾는 연산
• Union(x, y) : x, y를 포함하는 두 집합을 통합하는 연산

 

구현

def make_set(x):
    p[x] = x

def find_set_r(x):
    # 재귀로 푸는 경우
    if x == p[x]:
        return x
    return find_set(p[x])

def find_set(x):
    # 반복문으로 푸는 경우
    while x != p[x]:
        x = p[x]
    return x

def union(x, y):
    # 각각의 대표를 찾아서
    px = find_set(x)
    py = find_set(y)

    # x를 대표로 만든 것
    p[py] = px

N = 6
p = [0] * (N+1)

make_set(1)
make_set(2)
make_set(3)
make_set(4)
make_set(5)
make_set(6)

print(f'make_set() >> {p}')

union(1, 3)
print(f'union(1, 3) >> {p}')
union(2, 3)
print(f'union(2, 3) >> {p}')
union(5, 6)
print(f'union(5, 6) >> {p}')

print(f'find_set(6) : {find_set(6)}')


'''
make_set() >> [0, 1, 2, 3, 4, 5, 6]
union(1, 3) >> [0, 1, 2, 1, 4, 5, 6]
union(2, 3) >> [0, 2, 2, 1, 4, 5, 6]
union(5, 6) >> [0, 2, 2, 1, 4, 5, 5]
find_set(6) : 5
'''

 

 

union 함수를 실행한다고 해서 그룹 내 모든 원소에 대한 부모노드 정보가 바뀌는 것은 아님 !

>> 그룹의 개수를 세고 싶을 때는 해당 원소가 자기 자신을 가리키고 있을 때만 카운트 ~

cnt = 0
    for i in range(1, N+1):
    	# 대표하는 값이 자기 자신일때만
        if p[i] == i:
            cnt += 1

 

 

 

 

연습문제 - SWEA_7465_창용 마을 무리의 개수

 

SW Expert Academy

 

 

 

코드

def find_set(x):
    while p[x] != x:
        x = p[x]
    return x

def union(x, y):
    px = find_set(x)
    py = find_set(y)

    p[py] = px


T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())

    p = [i for i in range(N+1)]

    for _ in range(M):
        a, b = map(int, input().split())

        if a > b:
            union(a, b)
        else:
            union(b, a)

    cnt = 0
    for i in range(1, N+1):
    	# 자기 자신을 부모로 갖는 노드만 카운트 해주기
        if p[i] == i:
            cnt += 1

    print(f'#{test_case} {cnt}')

 

 

 

 

 

 

한국인지 캐나다인지,,, 아무도 모를,,,

 

내 행복을 묻는 사람이 있어 감사한 밤.

옆 사람의 행복을 궁금해 하는 것 만큼 사랑스러운 마음이 또 있을까?  귀엽군 ㅎ

신나게 대답해주고 싶어서 그 순간부터 나는 행복한 사람이기로~