[BOJ/python] 1043: 거짓말 (+ 분리 집합)

문제

✔️ gold 4
자료 구조
그래프 이론
그래프 탐색
분리 집합

문제 흐름

노드(사람)들 사이에 "파티"라는 연결점이 있다는 부분에서 최근에 풀었던 환승(boj_5214)의 하이퍼튜브가 생각났다. 이 문제에서도 역들을 잇는 하이퍼튜브들이 주어지는데, 이를 가상의 노드로 보고 거쳐가도록 그래프를 구성했었다. 이 문제에서도 같은 아이디어를 적용했다.

그래프에서 1번 부터 n번 까지는 사람들, n+1번 부터 n+m번 까지는 파티로 놓고 파티와 사람들을 연결하도록 했다.
그리고 BFS를 통해 탐색을 진행하는데 파티가 탐색될 때마다 그 수를 res에 카운트하고 최종적으로 전체 파티의 수에서 탐색된 파티(진실을 아는 사람들이 참석한 파티)를 뺀 뒤 리턴한다.

나는 현재 그래프 문제집을 풀고있기 때문에 당연히 그래프를 이용해 푸는 문제라고 생각했다.
물론 그래프 문제도 맞고 내가 푼 풀이도 정답을 받았지만, 막상 받고 알고리즘 분류를 확인해보니 분리 집합이라는 게 있었다. 처음보는 유형이었다!

ChatGPT를 이용해서 간단하게 분리 집합에 대해서 알아보고 그 내용을 정리했다.

분리집합 (Disjoint Set)

• 정의
  서로 겹치지 않는 여러 개의 집합을 효율적으로 관리하는 자료구조
  그래프 이론에서 서로 연결되어 있는 요소들을 그룹화할 때 유용
  대표적으로 최소 신장 트리를 구하는 크루스칼(Kruskal) 알고리즘에서 사용

• 주요 연산

  • Find(찾기)
    어떤 원소의 집합을 찾는 연산
    집합은 하나의 대표 원소(루트노드)를 가짐
    특정 원소의 대표 원소를 찾아 집합을 찾음
  • Union(합집합)
    두 집합을 하나의 집합으로 합치는 연산
    Find 연산을 통해 각 집합의 대표 원소를 찾고, 두 대표 원소를 같은 집합으로 만듦

• 최적화 기법

  • Path Compression(경로 압축)
    Find 연산시 탐색 경로상의 모든 노드를 해당 집합의 대표 노드와 직접 연결하는 방식
  • Union by Rank(랭크에 따른 합치기)
    Union 연산시 트리 높이를 최소화하기 위해 더 작은 트리를 큰 트리에 붙이는 방식

  ➡️ Find 연산 속도 향상

• 시간 복잡도 (n = 노드의 수)

  • 최적화가 적용되지 않은 경우
    • find
      트리의 높이에 비례하여 작동
      최악의 경우(편향된 트리) O(n)
    • union
      두 루트노드를 찾는 과정에서 find 연산 필요 -> find 연산이 수행시간 지배
      최악의 경우 O(n)
  • 최적화가 적용된 경우
    두 연산 모두 O(α(n)) ➡️ 실질적으로 상수 시간에 가까운 성능

코드

# 거짓말
# graph

import sys
from collections import deque
input = sys.stdin.readline

def bfs(g: list, s: list, n: int, m: int):
    vst = [0 for node in range(len(g))]
    res = 0
    for sx in s:
        q = deque([sx])
        vst[sx] = 1
        while q:
            x = q.popleft()
            for nx in g[x]:
                if vst[nx]:
                    continue
                q.append(nx)
                vst[nx] = 1
                if nx >= n+1:
                    res += 1
    return m-res

if __name__ == "__main__":
    n, m = map(int, input().split())
    g = [[] for node in range(n + m + 1)]
    t = list(map(int, input().split()))
    t = t[1:]
    for party in range(n+1, n+1+m):
        people = list(map(int, input().split()))
        people = people[1:]
        for p in people:
            g[p].append(party)
            g[party].append(p)

    result = bfs(g, t, n, m)
    print(result)

마무리

분리 집합을 막상 정리하고나니 크루스칼 알고리즘에 대해 들으면서 아 여기 쓰이던게 이거구나 싶었다.
가볍게 봤지만 다시 정리하고 개념을 다지는 좋은 기회가 됐다.
크루스칼 알고리즘 정리할 때 다시 생각날 듯. 또 읽어보면 좋을 것 같다.

그리고 이번 코드가 유독 변수명을 잘 못지은 것 같다. 다른 코드라고 잘 지어줬던건 아니지만..

그리고!! 집합을 이용해서 푸신 분의 풀이도 링크를 올려본다.
확실히 훨씬 깔끔하고 논리적으로 이해도 더 쉬운 것 같다.