목록2024/11/26 (1)

감자는 아직 꿈을 꾼다.

[백준-JAVA] 1717번 집합의 표현

알고리즘 : 유니온 파인드 유니온 파인드는 말그대로 합치기와 탐색입니다.여기서 상호 배타적인 집합 관계가 나옵니다. 말 그대로 둘이 어떠한 교집합도 없는 집합입니다.그래프로 생각하면 둘이 완전히 분리된 그래프 인거죠. 파인드는 자기 자신의 부모로 계속 올라가서 루트 노드까지 가는 과정이고 여기에서 만약 서로 다른 두 점을 파인드 했는데 루트 노드가 같을 경우는 이미 같은 집합 인것이고다를 경우는 다른 집합인 것이겠죠 유니온은 말 그대로 두 집합을 합치는 과정인데 여기서 중요한 게 깊이 차이를 신경써야됩니다.그냥 막무가내로 붙여버리면 깊이가 깊어져서 비효율적이게 됩니다.그래서 두 루트노드의 랭크를 확인해서 더 큰 랭크인 루트노드를 부모 루트 향하게 작은 랭크의 루트노드를 바꿔주면 트리의 깊이 차가 안생기므..
코테적 감자/백준 2024. 11. 26. 13:04
이전 Prev 1 Next 다음