니 위로 다 집합
(따라하시면 안됩니다.)
📃 예시 문제
데브코스 할 때, 나왔던 카카오 기출 문제인데...
전에 백준을 하루에 한문제씩 풀 때는 그래도 감이란게 조금은 있었는데 ㅠㅠㅠㅠ
지금은 싸악 사라졌다....
그래서 기출들 위주로 풀면서 다시 감을 찾고 있는데,
아무리 해도 안풀려서 답을 봤다...
결론적으로는 수식을 이용해서 풀긴 했는데,
내 생각으로는 집합을 이용해서도 풀 수 있지 않을까?
해서! 집합 알고리즘인 Union-Find를 알아보고자 한다.
📍설명
Union (유니온)
보통 연합, 조합 등을 의미하는 영어 단어
수학계열에선 합집합 이라고 한다.
즉, 직역하면 합집합 찾기가 된다.
대표적인 Graph 알고리즘으로, 두 Node가 같은 집합에 속하는지 판별하는 알고리즘이다.
반대로 서로 연결되어 있지 않은 노드를 판별할 수도 있기 때문에 서로소 집합 (Disjoint-set) 이라고도 한다.
흐름
코드는 크게 두 덩어리가 있다.
// Root 노드 찾기
public static int find(int x) {
if (x == parent[x]) return x; // 같으면 루트노드
parent[x] = find(parent[x]); // 재귀로 부모노드 접근
return parent[x];
}
// Union (합치기)
public static void union(int x, int y) {
// 각 부모노드를 비교
x = find(x);
y = find(y);
// 합하기
if (x != y) { parent[y] = x; }
}기준 Node가 되는 Root 노드를 찾는 find()
그리고 같은 집합에 속해야 하면, 합집합 해버리는 union()
만약 이러한 그래프가 있다고 가정하자.
저 위에 예시문제의 그래프를 그대로 가져왔다.
parent 배열이다.
값은 index 번호가 정점의 번호가 되고, 값은 부모(root) 정점의 번호가 들어간다.
기본적으로는 일단 본인이 아직 연결이 안되어 있다고 가정하고,
초기값은 index 번호가 된다. (내 자신이 일단 내 부모)
(3 -> 8)인 간선과 정점 정보가 추가되었다고 하면,
8의 부모값은 3이 된다.
그 다음, (3 -> 5)로 가는 간선 정보가 추가되면..
(5 -> 3)으로 가는 간선정보 추가하면!
이미 find(5)는 3이 나오게 되고 (부모가 3)
3번 정점 역시 find(3)을 하게 되면 3이 나온다.
저 표에선 3이 Root가 되고, {3, 5, 8}이 한 집합이 된다.
우측 표는 귀찮아서 패스~!
최종적으로는 표가 이리 된다.
2번 정점, 4번 정점은 없으니 그대로이고,
나머지 집합은 루트가 11이고 {1, 6, 7, 9, 10, 11, 12}가 한 집합이 된다.
주의!
{3, 5, 8} {1, 6, 7, 9, 10, 11, 12}
집합 내의 원소들은 절대 달라질 수가 없다.
그러나, "간선과 정점의 정보가 어느 순번대로 들어가냐?"
에 따라 Root(부모)는 달라질 수 있다.
보면 7과 12의 부모가 1로 되어 있다.
하지만 1의 부모는 여전히 11이다.
부모의 부모도 우리 가족이지 않는가? (할아버지, 할머니도 우리 가족이다 --)
그러니 같은 집합이다
그냥 단순하게 같은 집합인지만 판별하는 문제면 신경을 안써도 되지만,
문제 조건에서 부모(루트) 노드도 필요한 경우, 한번씩만 더 union()을 진행하면 된다.
