티스토리 뷰
언제 사용하는가?
최소 공통 조상 알고리즘은 트리에서 두 노드의 최단거리를 찾고 싶을때 사용한다.
시간복잡도는 O(logN)이며, 희소배열을 이해한다면 최소 공통조상은 응용이기 때문에
쉽게 이해 할 수 있다.
희소배열에 대해 알고 싶다면 하단의 링크를 참조하면 된다.
https://0bliviat3.tistory.com/79
[자료구조] 희소 배열 (Sparse Table)의 구현(JAVA)
언제 사용하는가 희소배열은 최소 범위 쿼리(Range Minimum Query)의 연산을 수행시 짧은 구현과 빠른 속도로 처리 하고 싶을때 사용하는 자료구조이다. 먼저 최소 범위 쿼리부터 알아보도록 하자. htt
0bliviat3.tistory.com
공통 조상이란?
먼저 최소 공통 조상의 개념부터 정의하고 넘어가도록 하겠다.
일단 위키부터 살펴보도록 하자.
Lowest common ancestor - Wikipedia
From Wikipedia, the free encyclopedia Tree node with two other nodes as descendants In this tree, the lowest common ancestor of the nodes x and y is marked in dark green. Other common ancestors are shown in light green. In graph theory and computer science
en.wikipedia.org
위키에서 보면 트리에서의 노드 자기 자신을 자손이라고 정의할때,
임의의 두 노드 a, b를 동시에 자손으로 갖는 노드를 공통조상이라고 한다.
이런 공통조상은 여러개가 존재할수 있는데 그 중에서도 가장 낮은 위치에 존재하는 공통 조상을
최소 공통 조상이라고 한다.
간단한 예시를 들어 설명하자면 다음과 같은 트리가 존재한다고 가정하겠다.
그리고 6번 노드와 5번 노드의 공통 조상을 찾으라고 하면, 1번 노드와 2번 노드를 찾을수 있다.
그중에서도 가장 낮은 공통조상인 2번 노드가 최소 공통 조상이 되는것이다.
또 다른 예로 4번 노드와 6번 노드의 공통조상은 1,2,4 번 노드가 공통조상이된다.
정의에서 나와있듯 노드자기 자신도 자손으로 생각하기 때문이다.
따라서 이 경우의 최소 공통조상은 4번 노드가 된다.
그럼 이제 최소 공통조상을 O(logN)의 시간복잡도로 구할수 있는 알고리즘을 정리해보도록 하겠다.
최소 공통 조상 알고리즘
최소공통조상 알고리즘은 다음과 같은 순서로 진행된다.
1. 각 노드의 깊이를 설정한다.
2. 모든 노드의 2^i 번째 부모노드를 찾는다.
3. 최소 공통 조상을 찾을 두 노드를 설정한다.
4. 두 노드의 깊이를 거슬러 올라가면서 동일하게 맞춘다.
5. 루트에서 내려오며 두노드의 공통조상을 찾는다.
그럼 그림을 통해 해당 과정을 설명하도록 하겠다.
다음과 같은 그래프가 있다고 가정하겠다.
각 노드의 깊이를 구한다면 다음과 같다.
그리고 모든 노드의 2^i번째 부모노드를 찾는다.
이때 부모노드를 찾는과정은 이전 포스팅에서 정리했던 희소 배열을 사용해 찾으면 된다.
18번 노드의 2^i번째 부모노드를 찾아 저장한다면 다음과 같이 저장될것이다.
18번 노드와 6번 노드의 공통조상을 찾는다 가정하면,
18번 노드의 깊이는 4, 6번 노드의 깊이는 3이므로 두 노드의 깊이를 동일하게 맞추면,
18번 노드는 15번 노드로 거슬러 올라간다.
그리고 루트에서 내려오면서 부모노드가 달라지는 지점을 찾는다.
달라지는 지점의 부모노드가 곧 최소 공통 조상이 되겠다.
따라서 이 경우 노드 2가 최소공통조상이다.
그럼 소스로 이 과정을 구현하며 정리해보도록 하겠다.
구현
먼저 필드로 트리의 정보, 희소배열, 각노드의 깊이를 저장할 자원을 선언해주도록 하겠다.
트리정보는 생성자를 통해 주입받아 사용하겠다.
public class LCA {
private final List<List<Integer>> tree; // 트리
private int[][] parents; // 각노드의 부모 노드 정보
private int[] depths; // 각노드의 깊이 정보
private boolean[] visit; // dfs를 위한 방문 배열
public LCA(final List<List<Integer>> tree) {
this.tree = tree;
}
}
희소배열의 크기를 설정하기 위해 트리의 높이를 구해주는 메소드를 하나 만들어 주겠다.
/**
* 트리의 높이 구하기
* @param n : 노드의 개수
* @return 높이
*/
public int getHeight(int n) {
return (int) Math.ceil(Math.log(n) / Math.log(2)) + 1;
}
그리고 초기화 메소드도 작성해준다.
public void clear(int n, int h) {
depths = new int[n + 1];
visit = new boolean[n + 1];
parents = new int[n + 1][h];
}
이제 각 노드의 깊이를 저장하며 현재 노드의 바로 윗부모와 연결하는 메소드를 작성해준다.
깊이우선탐색을 사용한다면 간단히 작성할수 있다.
/**
* 깊이를 저장하고, 윗부모와 연결하는 메소드
* @param node : 현재 노드
* @param depth : 깊이
*/
public void dfs(int node, int depth) {
visit[node] = true;
depths[node] = depth;
for(int next : tree.get(node)) {
if(visit[next]) {
continue;
}
parents[next][0] = node;
dfs(next, depth + 1);
}
}
희소배열을 채워줄 메소드도 작성해준다.
모든 노드의 2^i 번째 부모노드로 채운다. 이때 동적 프로그래밍을 사용한다.
/**
* 모든 노드의 2^i 번째 부모노드 채우기
* @param n : 노드의 수
* @param h : 높이
*/
public void setParent(int n , int h) {
for(int j = 1; j < h; j++) {
for(int i = 1; i <= n; i++) {
parents[i][j] = parents[parents[i][j - 1]][j - 1];
}
}
}
마지막으로 두 노드를 인자로 받아 최소 공통조상을 구하는 메소드를 작성하도록 하겠다.
먼저 더 깊은 노드를 찾아 기준을 잡을 것이다.
public int lca(int a, int b, int h) {
if(depths[a] < depths[b]) { // 더 깊은 노드를 a로 둔다.
int temp = a;
a = b;
b = temp;
}
}
그리고 거슬러 올라가며 노드의 깊이를 동일하게 맞춰준다.
public int lca(int a, int b, int h) {
if(depths[a] < depths[b]) { // 더 깊은 노드를 a로 둔다.
int temp = a;
a = b;
b = temp;
}
for(int i = h - 1; i >= 0; i--) { // 노드의 깊이를 동일하게 맞추기
if(depths[a] - depths[b] >= (1 << i)) {
a = parents[a][i];
}
}
}
이때 동일하게 맞춘 노드가 동일한 경우 해당 노드가 최소 공통 조상이다.
public int lca(int a, int b, int h) {
if(depths[a] < depths[b]) { // 더 깊은 노드를 a로 둔다.
int temp = a;
a = b;
b = temp;
}
for(int i = h - 1; i >= 0; i--) { // 노드의 깊이를 동일하게 맞추기
if(depths[a] - depths[b] >= (1 << i)) {
a = parents[a][i];
}
}
if(a == b) {
return a;
}
}
동일하지 않은 경우, 부모노드로 거슬러 올라가며 부모노드가 동일하지 않다면 갱신해준다.
그리고 더이상 갱신되지 않고 반복문을 빠져나왔을때의 부모노드가 곧 최소 공통 조상이다.
/**
* 두 노드의 최소 공통조상 구하기
* @param a : 노드1
* @param b : 노드2
* @param h : 트리의 높이
* @return 최소공통조상
*/
public int lca(int a, int b, int h) {
if(depths[a] < depths[b]) { // 더 깊은 노드를 a로 둔다.
int temp = a;
a = b;
b = temp;
}
for(int i = h - 1; i >= 0; i--) { // 노드의 깊이를 동일하게 맞추기
if(depths[a] - depths[b] >= (1 << i)) {
a = parents[a][i];
}
}
if(a == b) {
return a;
}
for(int i = h - 1; i >= 0; i--) {
if(parents[b][i] != parents[a][i]) { // 부모노드로 거슬러 올라가기
a = parents[a][i];
b = parents[b][i];
}
}
return parents[a][0];
}
그럼 테스트용트리를 만들어 넣어보고, 예로 들었던 두 노드의 최소 공통 조상을 찾아보도록 하겠다.
public static void main(String[] args) {
List<List<Integer>> tree = new ArrayList<>();
for(int i = 0; i <= 18; i++) {
tree.add(new ArrayList<>());
}
tree.get(1).add(2);
tree.get(1).add(3);
tree.get(2).add(13);
tree.get(2).add(4);
tree.get(2).add(5);
tree.get(3).add(7);
tree.get(13).add(14);
tree.get(13).add(15);
tree.get(14).add(16);
tree.get(14).add(17);
tree.get(15).add(18);
tree.get(4).add(6);
tree.get(7).add(8);
tree.get(7).add(9);
tree.get(8).add(10);
tree.get(8).add(11);
tree.get(10).add(12);
LCA lca = new LCA(tree);
int h = lca.getHeight(18);
lca.clear(18, h);
lca.dfs(1, 0);
lca.setParent(18, h);
System.out.print(lca.lca(6, 18, h));
}
앞서 설명한 18번 노드의 6번 노드의 공통조상이 2임을 확인 할 수 있다.
다음은 코드의 전문이다.
package algorithm;
import java.util.ArrayList;
import java.util.List;
public class LCA {
private final List<List<Integer>> tree; // 트리
private int[][] parents; // 각노드의 부모 노드 정보
private int[] depths; // 각노드의 깊이 정보
private boolean[] visit; // dfs를 위한 방문 배열
public LCA(final List<List<Integer>> tree) {
this.tree = tree;
}
public void clear(int n, int h) {
depths = new int[n + 1];
visit = new boolean[n + 1];
parents = new int[n + 1][h];
}
/**
* 트리의 높이 구하기
* @param n : 노드의 개수
* @return 높이
*/
public int getHeight(int n) {
return (int) Math.ceil(Math.log(n) / Math.log(2)) + 1;
}
/**
* 깊이를 저장하고, 윗부모와 연결하는 메소드
* @param node : 현재 노드
* @param depth : 깊이
*/
public void dfs(int node, int depth) {
visit[node] = true;
depths[node] = depth;
for(int next : tree.get(node)) {
if(visit[next]) {
continue;
}
parents[next][0] = node;
dfs(next, depth + 1);
}
}
/**
* 모든 노드의 2^i 번째 부모노드 채우기
* @param n : 노드의 수
* @param h : 높이
*/
public void setParent(int n , int h) {
for(int j = 1; j < h; j++) {
for(int i = 1; i <= n; i++) {
parents[i][j] = parents[parents[i][j - 1]][j - 1];
}
}
}
/**
* 두 노드의 최소 공통조상 구하기
* @param a : 노드1
* @param b : 노드2
* @param h : 트리의 높이
* @return 최소공통조상
*/
public int lca(int a, int b, int h) {
if(depths[a] < depths[b]) { // 더 깊은 노드를 a로 둔다.
int temp = a;
a = b;
b = temp;
}
for(int i = h - 1; i >= 0; i--) { // 노드의 깊이를 동일하게 맞추기
if(depths[a] - depths[b] >= (1 << i)) {
a = parents[a][i];
}
}
if(a == b) {
return a;
}
for(int i = h - 1; i >= 0; i--) {
if(parents[b][i] != parents[a][i]) { // 부모노드로 거슬러 올라가기
a = parents[a][i];
b = parents[b][i];
}
}
return parents[a][0];
}
public static void main(String[] args) {
List<List<Integer>> tree = new ArrayList<>();
for(int i = 0; i <= 18; i++) {
tree.add(new ArrayList<>());
}
tree.get(1).add(2);
tree.get(1).add(3);
tree.get(2).add(13);
tree.get(2).add(4);
tree.get(2).add(5);
tree.get(3).add(7);
tree.get(13).add(14);
tree.get(13).add(15);
tree.get(14).add(16);
tree.get(14).add(17);
tree.get(15).add(18);
tree.get(4).add(6);
tree.get(7).add(8);
tree.get(7).add(9);
tree.get(8).add(10);
tree.get(8).add(11);
tree.get(10).add(12);
LCA lca = new LCA(tree);
int h = lca.getHeight(18);
lca.clear(18, h);
lca.dfs(1, 0);
lca.setParent(18, h);
System.out.print(lca.lca(6, 18, h));
}
}'알고리즘 > 구현' 카테고리의 다른 글
| [자료구조] 희소 배열 (Sparse Table)의 구현(JAVA) (0) | 2024.02.04 |
|---|---|
| 위상 정렬(Topology Sort)의 구현(JAVA) (1) | 2024.01.14 |
| 크루스칼(Kruskal) 알고리즘의 구현 (JAVA) (0) | 2024.01.01 |
| Union-Find 알고리즘의 구현 (JAVA) (0) | 2023.12.10 |
| 플로이드 와샬 알고리즘 (JAVA) (1) | 2023.11.27 |