무방향 그래프와 서로소 집합

무방향 그래프와 서로소 집합

 

서로소 집합의 필요성을 이해하기 위해서 아래 문제를 읽어보자.

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

1043번: 거짓말

 

문제를 읽어보면 진실을 알고 있는 사람이 포함된 파티와 포함되지 않은 파티로 나누고 싶을 것이다.

바이러스가 전염되는 것처럼 진실을 알고 있는 사람이 포함된 파티(그래프)는 모두 진실을 알게 된다.

하지만 단절된 그래프는 전염되지 않기도 하다.

 

위와 같은 상황에서 서로소 집합의 개념을 적용할 수 있다.

서로 다른 파티들이 연쇄작용을 일으켜 파티에서 만난 사람들이 그래프처럼 이어진다.

그래프들은 서로 중복된 원소를 갖지 않는 서로소 집합이다.

우리는 이 그래프를 찾아 진실을 아는 사람이 포함된 집합를 찾으면 된다.

 

서로소 집합의 구현

서로소 집합의 구현은 union과 find로 할 수 있다.

union은 합집합으로 두 집합을 연결한다.

위 예시에 적용하면 한 파티에서 생긴 집합과 다른 파티를 통해 생긴 집합이 공동의 원소를 가진다면

두 집합을 하나로 만드는 것이다.

 

find는 서로소 집합의 구현이 트리를 이용하기 때문에 필요하다.

union을 통해 두 집합이 하나의 집합으로 표현되는 과정에서 트리 구조를 이용하여

한 집합의 루트 노드가 다른 집합의 노드를 가리키도록 한다.

결과적으로 두 집합의 모든 원소는 하나의 루트 노드를 가리키게 된다.

다시 말하면, 노드가 서로 같은 집합에 포함되었음을 파악하기 위해서는

노드의 루트 노드를 찾아 비교하면 된다는 것이다.

 

첫 번째 풀이, 서로소 집합을 몰랐을 때

import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
knowns = set(map(int, input().split()[1:]))
party = [list(map(int, input().split()[1:])) for _ in range(M)]
visited = [False] * (N+1)

q = list(knowns)
while q:
    known = q.pop()
    visited[known] = True
    
    for attendees in party:
        if known in attendees:
            for attendee in attendees:
                if not visited[attendee]:
                    knowns.add(attendee)
                    q.append(attendee)

result = 0
for attendees in party:
    flag = True
    for known in knowns:
        if known in attendees:
            flag = False
            break
    if flag:
        result += 1

print(result)

 

각 파티를 순회하면서 진실을 알고 있는 사람을 만나면 queue에 push하고 다시 각 파티를 순회한다.

파티에 참여한 모든 사람들에 대해 파티를 순회하면서 검사하므로 비효율적이다.

 

두 번째 풀이, 서로소 집합을 find와 union으로 구현

import sys

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
known = set(map(int, input().split()[1:]))

parents = [None] + [i for i in range(1, N+1)]


def find_parent(child):
    if parents[child] != child:
        parents[child] = find_parent(parents[child])
    return parents[child]


def union(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        parents[y] = x
    else:
        parents[x] = y


def check_known(party):
    for p in party:
        if find_parent(p) in known:
            return False
    return True


# 파티 입력
# 파티 구성원들을 서로소 집합으로 연결
parties = []
for _ in range(M):
    party = list(map(int, input().split()[1:]))
    if len(party) != 1:
        for idx, p in enumerate(party[1:], start=1):
            union(party[idx - 1], party[idx])
    parties.append(party)

# 진실을 알고 있는 사람들의 root를 known에 추가한다.
tmp = set()
for k in known:
    k_parent = find_parent(k)
    tmp.add(k_parent)
known = tmp

result = 0
for party in parties:
    if check_known(party):
        result += 1
print(result)

 

find와 union을 통해 해결한 풀이이다.

 

세 번째 풀이,  집합의 성질을 이용한 풀이

import sys

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
known = set(map(int, input().split()[1:]))
parties = [set(map(int, input().split()[1:])) for _ in range(M)]

for _ in parties:
    for party in parties:
        if party & known:
            known |= party

result = 0
for party in parties:
    if not party & known:
        result += 1
print(result)

파이썬의 집합 연산을 이용해서 풀이했다.

합집합과 교집합을 이용한 것이 인상적이다.

 

이제 다른 문제를 풀어보자.

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

1976번: 여행 가자

 

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