BaekJoon 3584번 : 가장 가까운 공통 조상 (python)

📝 BaekJoon 3584번 : 가장 가까운 공통 조상 (G4 51.954%)

---

🔎 가장 가까운 공통 조상 문제

---

📌 아이디어

효율성이 필요없는 최소 공통 조상(LCA)알고리으로 해결할 수 있는 문제이다.

---

💭 풀이

• 두 노드의 최소 공통 조상을 찾기 위해서는 두 노드의 깊이 level갚을 동일하게 맞춰주고 두 노드를 root노드로 올려주면서 root노드가 같아질 때를 찾아준다.
• 먼저 두 노드의 level을 찾아주기 위해 root노드를 찾아 각 노드들의 level값을 계산해주고 입력 받은 두 노드 중 level이 더 큰 노드를 level이 작은 노드에 맞춰주고 같은 level에서 level을 하나씩 올려주며 같은 root노드를 만날 때 까지 반복한다.

---

💻 코드

from collections import deque
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T) :
    n = int(input())
    edge = [[] for _ in range(n+1)]
    own = [0]*(n+1)
    level = [0]*(n+1)
    root = set()
    for _ in range(n-1) :
        a, b = map(int,input().split())
        edge[a].append(b)
        own[b] = a
        root.add(b)

    t1, t2 = map(int,input().split())

    r = 0
    for i in range(1,n+1) :
        if i not in root :
            r = i
    
    q = deque([(r,0)])
    while q :
        x, count = q.popleft()
        level[x] = count

        for i in edge[x] :
            q.append((i,count+1))
    
    result = 0
    while True :
        if t1 == t2 :
            result = t1
            break
        if level[t1] > level[t2] :
            level[t1] -= 1
            t1 = own[t1]
        elif level[t1] < level[t2] :
            level[t2] -= 1
            t2 = own[t2] 
        else :
            level[t1] -= 1
            level[t2] -= 1
            t1 = own[t1]
            t2 = own[t2]
    print(result)

---