[코딩테스트 cheatsheet] 서로소 집합 (Disjoint set)

2023. 2. 23. 08:12·ps, cp/코딩테스트 cheatsheet

개념

서로소 집합 : 공통 원소가 없는 두 집합

서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

 

스택, 큐가 pop, push 연산을 사용하는 것 처럼 서로소 집합은 union, find 연산을 이용함

find - 속한 집합이 어떤 집합인지 찾기

union - 두 개의 집합을 합치기

 

싸이클인지 구하기 

find해서 같다면 cycle

다르면 union

코드

# find - 부모 찾기
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# union 두 집합의 부모를 비교, 더 작은 쪽을 부모로 대입
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 부모를 자기 자신으로 초기화, 문제에 따라 다름
for i in range(1, v + 1):
    parent[i] = i
    
# 입력마다 바로 union 해주면 됨
for _ in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)
    
# 마지막에 모든 노드에 대해서 find
for i in range(1, v + 1):
    find_parent(parent, i)
    
# cycle 구하기
cycle = False
for i in range(e):
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
    	cycle = True
        break
    else:
    	union_parent(parent, a, b)

 

백준 티어별로 살펴보는 문제 유형

 

골드 4

알면 풀리는 문제

1717 - 집합의 표현 (https://www.acmicpc.net/problem/1717)

 

골드 3

 

골드 2

살짝만 생각하면 풀리는 문제

10775 - 공항 (https://www.acmicpc.net/problem/10775)

'ps, cp > 코딩테스트 cheatsheet' 카테고리의 다른 글

[코딩테스트 cheatsheet] 다익스트라  (0) 2022.12.14
[코딩테스트 cheatsheet] 플로이드 워셜  (0) 2022.12.10
[코딩테스트 cheatsheet] 시작하기  (0) 2022.12.09
'ps, cp/코딩테스트 cheatsheet' 카테고리의 다른 글
  • [코딩테스트 cheatsheet] 다익스트라
  • [코딩테스트 cheatsheet] 플로이드 워셜
  • [코딩테스트 cheatsheet] 시작하기
uzzam
uzzam
  • uzzam
    uzzam.dev
    uzzam
  • 전체
    오늘
    어제
    • 분류 전체보기 (55)
      • blockchain (6)
        • geth 소스코드 분석 (4)
        • solidity (0)
      • blockchain (리서치) (1)
      • blockchain (투자) (2)
      • 프로젝트 - 뮤피 (0)
      • 프로젝트 - 담타 (9)
        • 소개 (1)
        • 프로젝트 관리하기 (4)
        • 리팩터링 (3)
        • etc. (1)
      • CS (0)
        • 운영체제 (0)
      • ps, cp (5)
        • 코딩테스트 cheatsheet (4)
        • baekjoon (1)
        • codeforces (0)
      • languages (2)
        • dart (1)
        • swift (1)
        • go (0)
      • frameworks (5)
        • flutter (5)
        • spring (0)
      • ios (2)
      • 블로그 (10)
      • git (2)
      • cloud (5)
      • etc. (6)
      • linux (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    디버깅
    go-ethereum
    geth
    이더리움
    geth 분석
    flutter
    멀티디바이스
    블로그
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
uzzam
[코딩테스트 cheatsheet] 서로소 집합 (Disjoint set)
상단으로

티스토리툴바