최소 공통 조상(LCA, Least Common Ancestor)

나이브한 방식의 최소 공통 조상 찾기

def solution(N, tree, v1, v2):

    level = [0 for i in range(N+1)]
    parent = [0 for i in range(N+1)]
    visited = [0 for i in range(N+1)]

    def dfs(here, depth):
        visited[here] = True
        level[here] = depth
        for there in tree[here]:
            if not visited[there]:
                parent[there] = here
                dfs(there, depth+1)

    root = 1 #root 1로 가정
    dfs(root, 1)

    def LCA(v1, v2):
        """ 
        v1, v2의 공통조상을 찾아주는 알고리즘 
        """
        #같은 레벨로 만들어 준다.
        while level[v1] != level[v2]:
            if level[v1] > level[v2]:
                v1 = parent[v1] #위의 레벨로 올려준다.
            else:
                v2 = parent[v2] 

        #위가 진행되면 v1과 v2의 레벨이 같아짐
        #이 상태에서 v1 != v2라면 레벨을 한개씩 올리면서 같은지 확인 같으면 LCA

        while v1 != v2:
            v1 = parent[v1]
            v2 = parent[v2]

        return v1

    return LCA(v1, v2)