Union Find

문제 https://leetcode.com/problems/path-existence-queries-in-a-graph-i 풀이 그래프 각 노드의 연결 조건이 주어지고, 들어오는 쿼리들에 있는 두 노드들이 연결되어있는지 확인하는 문제이다. queries 배열의 길이가 최대 10만이므로, BFS를 이용해서 풀기는 거의 불가능하다. BFS보다 더 빠르게 ‘연결 여부만’ 확인하는 방법은 Union-Find Set을 사용하면 된다. 우선 연결 조건은 두 노드의 절대 차이(노드 번호의 차이의 절대값)가 maxDiff 이하여야 하는데, 문제에서 nums 배열이 오름차순으로 정렬되어 있다고 했으므로, nums[j] - nums[i] <= maxDiff 를 만족하는 연속된 범위를 투 포인터로 찾을 수 있다. ...

문제 https://www.acmicpc.net/problem/4195 풀이 전형적인 Union-Find 문제이지만, 각 원소들이 정수가 아닌 문자열로 구성되어 있는 특징이 있다. 정수를 문자열로 대응시키는 것은 Dictionary를 쓰면 쉽게 할 수 있으므로 다음과 같은 방식으로 알고리즘이 진행된다 입력값(문자열 2개)에 대해 각 문자열이 Dictionary에 대응되는 Value가 있는지 판단한다. 1에서 없다면 Dictionary에 [String:Integer] 꼴로 매핑한다. 있다면 그냥 넘어간다. 매핑이 끝났다면, 들어온 두 문자열로 union(a, b) 연산을 하고 그 집합 내부의 원소의 개수를 카운트한다. 여기서 문제는 3번이다. 어떻게 해야 효율적으로 집합 내부의 원소를 카운트 할 수 있을까? ...