가장 가까운 공통 조상

https://www.acmicpc.net/problem/3584

조금 쉬운 문제다

두 노드에서 공통된 가장 가까운 부모를 찾는 문제

setrecursionlimit을 안 걸어줬다가 recursionerror로 몇번 반려당했다

import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline

tk = int(input())


def find_parent(x, res, depth):
    res.append((x, depth))
    if len(tree[x]) == 0:
        return
    for i in tree[x]:
        find_parent(i, res, depth + 1)


for _ in range(tk):
    n = int(input())
    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        tree[b].append(a)
    targeta, targetb = map(int, input().split())
    resa, resb = [], []
    find_parent(targeta, resa, 0)
    find_parent(targetb, resb, 0)
    f = False
    for i in resa:
        if f:
            break
        for j in resb:
            if i[0] == j[0]:
                print(i[0])
                f = True
                break

처음 해결할 때 탐색 시작하는 노드를 resa, resb에 안 넣어줘서 틀린 출력이 나왔었다

find_parent 함수의 for 문 내부에서 res에 결과를 append하고 있었기 때문

그래프는 연결된 숫자를 눈으로만 봐서는 트리가 어떻게 생겼는지 알기 어렵기 때문에 그려보면 쉽게 풀 수 있다

또 이미 정렬되어 있는지 depth 를 추가해서 나중에 depth 기준으로 정렬하고 비교하는 로직을 추가했었는데

이미 정렬이 되어있는지 sort를 없애도 맞았다

밑에서 답을 찾는 거 이중for로 찾고 싶지는 않았는데 (투포인터같은 거 쓸 수 있을 것 같이 생겼다)

이미 재귀가 들어간 시점에서 배열 두개 비교하는 시간이 추가된다고 의미가 있나 싶긴 하다