![[1717번] 집합의 표현](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbit6sg%2Fbtqw6oWcWMU%2FkrskkKgMLJgSWd8P2WBd31%2Fimg.png)
1717번: 집합의 표현
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a
www.acmicpc.net
유명한 자료구조 중 하나인 '유니온 파인드(혹은 Disjoint-Set, 상호 배타적 집합,... 등등)'를 이해하고 사용하는 문제입니다.
먼저 무슨 자료구조인지부터 알아보도록 할까요?
[TWpower's Tech Blog의 '유니온 파인드']
사실 위의 링크에서 보신 내용으로 이 문제는 그냥 풀 수 있습니다.
즉, 유니온 파인드 자료구조를 구현할 수 있느냐 없느냐의 문제이기 때문에 이 자료구조를 익힐 수 있는 문제라 할 수 있습니다.
저는 위의 블로그에 있는 내용에서 조금 더 보태서 효과적인 방법을 하나 더 추가했습니다.
바로 '처음 배열의 값을 초기화'하는 부분입니다.
해당 블로그에서는 index와 같은 값으로 배열을 초기화시키고 있습니다.
하지만 그렇게 하면 root 노드가 가지는 정보는 index와 가지고 있는 값이 같다는 정보뿐이므로 그걸로 끝나게 됩니다.
여기서 우리는 root 노드가 좀 더 특별해질 수 있는 방법을 하나 추가하도록 하죠.
바로 root 노드는 자신의 child의 수를 저장하도록 하는 것입니다.
이렇게 하면 무슨 이득이 있을까요?
그렇습니다. 바로 Union시 더 적은 child를 가진 set을 더 많은 child를 가진 set으로 편입시킴으로써 Find 함수 사용 시 더 빠른 시간 내에 root 노드의 index를 찾을 수 있다는 장점을 가지는 것입니다!
그래서 초기화 시 -(child의 수)로 root들을 초기화 시키는 것이죠.
자 이제 '유니온 파인드'의 세계로 떠나보도록 합시다.