본문 바로가기

코딩테스트 준비

서로소 집합 알고리즘

find_parent(x) 메소드가 최상단 부모 노드를 바로 재귀적으로 찾아 반환해 준다. 이를 이용하는 union_parent(x, y) 메소드는 두 노드를 비교하여 작은 노드를 큰 노드의 부모 노드로 연결시킨다. 해당 문제는 연결 요소의 개수를 세는 문제이므로 union_parent(x, y)을 통해 연결을 끝낸 뒤 각 노드의 부모노드를 set 자료형 안에 담아서 해결했다.

'코딩테스트 준비' 카테고리의 다른 글

전위 순회, 중위 순회, 후위 순회  (0) 2021.02.24
재귀 + dp + 조합 공식  (0) 2021.02.24
itertools의 combinations를 이용한 부분수열 합 문제  (0) 2021.02.24
큐 자료구조 문제  (0) 2021.02.23
DP - 중  (0) 2021.02.22