이 문제는 처음에 Union-Find랑 비슷해보여서 그래프로 접근했다가 망한 케이스다.
이후에는 여러 풀이 방법을 생각해봤는데 너무 복잡해져서
간단하게 구현할 수 있는 방법이 무엇일까 검색하다가
빵똥님의 풀이법을 참고하게 됐다.
그리고 찾아보니까 코테에서는 함수형 프로그래밍은 굳이 안해도 되는 것 같다.
setParent()와 같은 함수는 그냥 바로 Main에 작성해도 될 것 같다.
알고리즘
트리: LCA
체감 난이도
★ ★ ★ ★ ☆
다시 풀 수 있는가?
NO
1. isVisited 체크
isVisited로 방문한 노드를 체크하고,
다른 노드의 조상을 찾을 때 체크한 노드를 마주하면 break 한다.
public void findCommonAncestor(int a, int b) {
while (a > 0) {
isVisited[a] = true;
a = tree[a];
}
while (b > 0) {
if (isVisited[b]) {
System.out.println(b);
break;
}
b = tree[b];
}
}
전체 코드 ▼
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ3584 {
int[] tree;
boolean[] isVisited;
public void setParent(int A, int B) {
tree[B] = A;
}
public void findCommonAncestor(int a, int b) {
while (a > 0) {
isVisited[a] = true;
a = tree[a];
}
while (b > 0) {
if (isVisited[b]) {
System.out.println(b);
break;
}
b = tree[b];
}
}
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
tree = new int[N+1];
isVisited = new boolean[N+1];
for (int j = 0; j < N-1; j++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
setParent(A, B);
}
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
findCommonAncestor(a, b);
}
}
public static void main(String[] args) throws Exception {
new BOJ3584().solution();
}
}