Algorithm & Data Structure
2022. 8. 16.
백준 - 1717번(유니온 파인드, 재귀, 집합)
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 자체가 이해가 어렵지는 않은 문제다. 이 문제를 풀기 위해서는 유니온 파인드가 뭔지 알아야 한다. 그래프 풀이법의 일종으로 볼 수 있다. 노드들을 합치고(union), 부모를 찾아준다(find) 일련의 과정은 다음과 같다. 1. 원소 두 개를 입력받고 Union 함수를 호출한다. 2. 입력받은 원소의 부모를 find 함수를 이용해서 '재귀적으로' 찾아..