문제 이해

(A,B) 쌍이 여러 개주어진다. A는 B의 부모 Node라는 뜻이다.
이러한 Node들로 Tree를 생성 할 수 있다.
마지막으로 (a,b) 쌍이 주어진다.

이 때 a와 b의 조상 Node 들 중 가장 가까운 공통 조상 Node 번호를 구하는 문제이다.

---

문제 풀이

이 문제에서는 자식 Node가 그렇게 중요하지 않다.
따라서, 나는 부모 Node에 신경을 많이 썼다.

Tree의 특성 중 "한 개의 Node는 1개 이하의 부모 Node를 가지고 있다"라는 것을 활용했다.

먼저 Node를 저장할 배열 공간을 준비했다.
이후 node[tmp] = node[i]를 저장했는데, 이 때 tmp의 부모는 i이다.
즉, node[자식 번호]에 저장된 값은 node[부모 번호]이다.
위에서 말했듯, 자식 하나 당 부모는 1개 이하만 존재하므로 List가 아닌 배열 형태로도 에러 없이 형성할 수 있다.
마지막으로, null값이 저장된 값이 하나 존재할텐데, 그 값은 Root Node이다.
(부모 Node가 0개인 Node는 Root Node밖에 존재하지 않는다)

(a,b) 쌍의 가장 가까운 공통 조상을 구하고 싶다.
먼저 a의 조상 node들을 모두 list에 집어 넣었다.
이후, list에서 차례대로 b ⇒ b의 부모 ⇒ b의 부모의 부모 ⇒ ... 순으로 검사하여, 처음으로 list에 존재하는 값을 찾았다.

우리는 a와 b로부터 Root Node까지 역으로 거슬로 올라갔기 때문에, 이런 방식을 활용해서 처음으로 발견한 공통 조상 Node의 값은 가장 가까운 공통 조상이라고 할 수 있을 것이다.

---

코드

import java.io.*;
import java.util.*;

class Node{
	int value;
	Node parent;
	
	public Node(int value) {
		this.value = value;
		this.parent = null;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static Node[] nodes;
	static boolean[] visit;

	static ArrayList<Integer> find_route(int tmp2) {
        // tmp2의 모든 조상 노드를 찾는 과정
		ArrayList<Integer> list = new ArrayList<>();
		
		Node current = nodes[tmp2];
		while(current!=null) { 
            // current = null -> 직전에 검사한 Node의 부모 Node가 null이다.
            // 즉, 직전에 검사한 Node는 Root Node였으므로 더 검사할 필요가 없음
			list.add(current.value);
			
			current = current.parent;
		}
		
		return list;
	}
	
	static void find_close(ArrayList<Integer> node, int second) {
		
		Node current = nodes[second];
		
		while(true) {
			if(node.contains(current.value)) {
                // 처음 발견된 공통값이 답이므로 바로 return을 통해 
                // 메서드를 종료시켜준다.
				sb.append(current.value).append("\n");
				return;
			}
			current = current.parent;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		
		for(int t =0;t<T;t++) {
			
			N = sc.nextInt();
			
			nodes = new Node[N+1];
			
			for(int i=1;i<N+1;i++) {
				nodes[i] = new Node(i);
			}
			
			for(int  i=0;i<N-1;i++) {
				int tmp1 = sc.nextInt();
				int tmp2 = sc.nextInt();
				
				nodes[tmp2].parent = nodes[tmp1];
				//Node[x] = x의 부모 -> tmp1이 tmp2의 부모
			}
			
			int first = sc.nextInt();
			int second = sc.nextInt();
			find_close(find_route(first),second);
			
			
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과