반응형
문제
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작
www.acmicpc.net
풀이
유니온 파인드로 풀이할 수 있는 문제입니다.
https://dev-mandos.tistory.com/296
[알고리즘] 유니온 파인드(Union-Find) (Swift)
유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음
dev-mandos.tistory.com
먼저 노드별로 부모노드를 값으로 가질 Int 배열을 선언해주고, 초기 값은 자기 자신의 번호를 가르키도록 하였습니다.
부모 노드를 찾을 수 있는 find 연산을 구현하였습니다.
합집합 연산을 구현하는 방식은 1과 2에 대해서 합집합 연산을 하게되면 1과 2의 부모를 찾고,
찾은 부모를 다른 노드의 자식으로 연결시키는 방식으로 구현할 수 있습니다.
소스코드
후기
유니온 파인드에 대해 이해하고 있다면 쉽게 풀 수 있는 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 4195 친구 네트워크 (Swift) (0) | 2023.05.16 |
|---|---|
| [BOJ] 백준 1976 여행 가자 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 4803 트리 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 1991 트리 순회 (Swift) (0) | 2023.05.15 |
| [BOJ] 백준 1967 트리의 지름 (Swift) (0) | 2023.05.15 |
