3584. 가장 가까운 공통 조상

문제

백준 3584번 가장 가까운 공통 조상

---

풀이

그렇게 어려운 난이도도 아닌데 접근 방식을 몰라서 못 풀었었다.

그냥 부모노드 정보만 저장해도 되는건데 계속 자식노드 정보를 저장하느라 어떻게 트리를 지지고 볶아야할지 한참을 고민하고 빙빙돌아갔다.

노드의 개수만큼 리스트를 0으로 초기화 한 뒤,
입력값을 받을 때 tree[자식노드] = 부모노드로 저장하면 루트노드까지 거슬러 올라가기 훨씬 수월해진다.

그렇게 저장한 트리정보로 while문을 통해 두 노드u, v의 조상들을 각각 리스트에 저장한 뒤, 리스트의 뒤에서부터 탐색해서 가장 가까운 공통 조상을 구한다.

T = int(input())
for _ in range(T):
    n = int(input())
    t = [0 for _ in range(n+1)]
    for _ in range(n-1):
        p, c = map(int, sys.stdin.readline().split())
        t[c] = p
    u, v = map(int, sys.stdin.readline().split())

    u_parent, v_parent = [u], [v]
    while t[u]:
        u_parent.append(t[u])
        u = t[u]
    while t[v]:
        v_parent.append(t[v])
        v = t[v]
    
    ui, vi = len(u_parent)-1, len(v_parent)-1
    while u_parent[ui] == v_parent[vi]:
        ui, vi = ui-1, vi-1
    print(u_parent[ui+1])

---

부족한점

그래프 문제 연습 필요