풀이
대표적인 Disjoin Set 문제이다.
일전에도 기본 Set이 아닌 Disjoin Set을 이용해 문제를 푼 경험이 있다.
[백준 1043] 거짓말 [Python]
풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(peop
kyr-db.tistory.com
문제에서 주어진 n + 1개의 집합은 Disjoin Set을 이용할 때 기본적으로 자신의 부모는 자신임을 나타내는 과정이다.
때문에 n + 1의 인덱스에 대해 자신의 인덱스로 초기화를 해주면 된다.
그 이후로는 문제에서 주어진대로 집합 a, b에 대해 입력을 받아 공통 부모를 갱신하거나,
공통 부모를 가지는지 확인해주면 된다.
만약 두 수가 가지는 부모가 동일하다면 공통 부모를 가지는, 즉 이미 동일한 집합과 동치이므로 "YES"이다.
소스코드
출처
1717번: 집합의 표현
초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 1976] 여행 가자 [Java] (0) | 2023.06.29 |
|---|---|
| [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] (0) | 2023.06.29 |
| [백준 13701] 중복 제거 [Java] (0) | 2023.06.27 |
| [백준 28235] 코드마스터 2023 [Python] (0) | 2023.06.25 |
| [백준 28270] Marked-Numbered [Python] (0) | 2023.06.25 |