풀이 방법
각 노드의 부모노드를 저장해주고 루트 노드는 그대로 0으로 두었다.
findHeight 메서드를 이용해서 두 노드의 높이를 구해주면서 루트 노드까지 가는 과정에서 만난 노드들의 높이도 저장해 주었다.
가까운 공통 조상을 구하기 위해 먼저 높이를 낮은 쪽으로 맞춰주고 한 칸씩 부모로 가면서 구해주었다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int[] tree, height;
static int T, N, a, b;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
N = Integer.parseInt(br.readLine());
tree = new int[N + 1];
height = new int[N + 1];
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
tree[b] = a;
}
st = new StringTokenizer(br.readLine());
System.out.println(NCA(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
}
static int findHeight(int a) {
int count = 1;
if (tree[a] != 0) {
count += findHeight(tree[a]);
}
height[a] = count;
return count;
}
static int NCA(int a, int b) {
findHeight(a);
findHeight(b);
if (height[a] < height[b]) {
int temp = a;
a = b;
b = temp;
}
while (height[b] < height[a]) {
a = tree[a];
}
while (a != b) {
a = tree[a];
b = tree[b];
}
return a;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
감시 - 15683번 (0) | 2022.02.18 |
---|---|
빵집 - 3109번 (0) | 2022.02.17 |
모래성 - 10711번 (0) | 2022.02.14 |
스타트링크 - 5014번 (0) | 2022.02.14 |
호텔 - 1106번 (0) | 2022.02.10 |