BOJ #3584
참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..)
🔖Solution
문제 제목에서도 주어진대로 가장 가까운 공통 조상(LCA)을 찾는 문제이다
🔖LCA Algorithm
모든 노드에 대하여 깊이(depth)
와 2^i번째 부모
에 대한 정보를 계산 (각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법, 즉 메모리를 더 사용하여 각 노드에 대하여 2^i
번째 부모에 대한 정보를 기록)
e.g.
다음과 같이 루트가 1로 고정되어 있고 각 연결된 두 정점에 대한 정보가 input으로 주어질 때, 두 정점의 가장 가까운 공통 조상을 구하는 문제를 풀어보자
먼저 각 연결된 두 정점에 대한 정보가 input으로 주어질 때 이를 저장한다. 각각
adj배열
에 저장된 값은 위에 있는 오른쪽 표와 같다.void init() { int from, to; cin >> N; for (int i = 0; i < N - 1; i++) { cin >> from >> to; adj[from].push_back(to); adj[to].push_back(from); } }
문제에서 루트가 1이라고 지정되어 있으므로 먼저 루트인 1번부터 부모와 레벨을 update힌다. (루트의 부모는 0번 노드라고 지정하고 루트 노드의 레벨은 1이다)
그 후 루트에서 연결된 다른 노드들을 순서대로 부모와 레벨을 update한다. 이 과정을 모든 노드에 반복한다.set_tree(1, 0); void set_tree(int node, int pnode) { // DFS로 트리 구성 parent[node] = pnode; level[node] = level[pnode] + 1; for (int i = 0; i < adj[node].size(); i++) { int child = adj[node][i]; if (child == pnode) continue; set_tree(child, node); } }
모든 노드들의 부모와 레벨을 저장한 후 가장 가까운 공통 조상을 구하고자 하는 두 정점을 입력받고 찾아낸다. 이때 두 정점의 레벨을 맞춰주고 (레벨이 같아질 때까지 루트에서 더 멀리 있는 노드를 위로 끌어올린다), 두 정점의 레벨이 같아졌을 때 두 정점의 부모가 같아질 때까지 같이 올라간다.
int lca(int a, int b) { //a를 더 level이 높은 정점으로 맞춤 if (level[a] < level[b]) { int tmp = a; a = b; b = tmp; } while (level[a] != level[b]) a = parent[a]; while (a != b) { a = parent[a]; b = parent[b]; } return a; }
🔖BOJ #3584
이 문제에서 더 추가됐던 점은 루트를 직접 구해야하는 것이다.
그래서 boolean[] rootCheck
변수를 두어 루트의 인덱스를 확인한다
package boj3584;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Solution2 {
static List<Integer>[] adj;
static int[] parent, level;
static boolean[] rootCheck;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader (new InputStreamReader(System.in));
StringTokenizer st=null;
int T=Integer.parseInt(br.readLine());
for (int tc=1; tc<=T; tc++) {
int N=Integer.parseInt(br.readLine());
parent=new int[N+1];
level=new int[N+1];
adj=new ArrayList[N+1];
for (int j=1; j<N+1; j++)
adj[j]=new ArrayList<>();
boolean[] rootCheck=new boolean[N+1];
Arrays.fill(rootCheck, true);
for (int i=0; i<N-1; i++) {
st=new StringTokenizer(br.readLine(), " ");
int A=Integer.parseInt(st.nextToken());
int B=Integer.parseInt(st.nextToken());
adj[A].add(B);
adj[B].add(A);
rootCheck[B]=false;
}
int rootIdx=0;
for (int k=1; k<N+1; k++) {
if (rootCheck[k]) {
rootIdx=k;
break;
}
}
setTree(rootIdx, 0);
st=new StringTokenizer(br.readLine()," ");
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
System.out.println(LCA(a,b));
}
}
static void setTree(int node, int pnode) {
parent[node]=pnode;
level[node]=level[pnode]+1;
for (int child : adj[node]) {
if (child != pnode) {
setTree(child, node);
}
}
}
static int LCA (int a, int b) {
if (level[a]<level[b]) {
int tmp=a;
a=b;
b=tmp;
}
while (level[a]!=level[b])
a=parent[a];
while (a!=b) {
a=parent[a];
b=parent[b];
}
return a;
}
}
Reference
https://velog.io/@shiningcastle/%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://www.crocus.co.kr/660