LCA ( 11437 번 )

11437번: LCA

 

---

🧠 알고리즘

• 최소 공통 조상 (LCA, Lowest Common Ancestor) — BFS 기반 전처리

 

✔️ 동작 방식

- 문제 핵심 아이디어
트리에서 두 노드의 공통 조상 중 가장 가까운(가장 깊은) 노드를 찾는 문제.
BFS로 각 노드의 부모(pt)와 깊이(depth)를 먼저 계산한 뒤,
두 노드의 깊이를 맞춘 후 위로 올라가며 같은 조상을 찾는다.

 

- 주요 로직 요약

[ 트리 연결 정보 구성 (_mk_conn) ]

• 입력으로 주어진 간선 정보를 바탕으로 인접 리스트 형태로 트리 구성
• 양방향 연결 저장 (a ↔ b)

[ 부모 및 깊이 계산 (_cr_pt_depth) ]

• 루트(1번 노드)에서 BFS 수행
• 각 노드의 부모(pt)와 깊이(depth)를 계산
• 방문하지 않은 노드는 pt[next_q] == -1 조건으로 판별

[ LCA 탐색 (_LCA) ]

• 두 노드 x, y 중 더 깊은 쪽을 부모 방향으로 올려 깊이를 맞춤
• 깊이가 같아진 뒤, 두 노드가 같아질 때까지 동시에 부모로 이동
• 결국 두 노드가 만나는 위치가 LCA

---

 

🧾 코드

import sys
from collections import deque

def _mk_conn(number):
    answer = [[] for _ in range(number + 1)]
    for _ in range(number - 1):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        answer[a].append(b)
        answer[b].append(a)

    return answer


def _cr_pt_depth():
    pt, depth = [-1] * (n + 1), [-1] * (n + 1)
    pt[1], depth[1] = 0, 0
    
    queue = deque([1])
    while queue:
        q = queue.popleft()
        for next_q in conn[q]:
            if pt[next_q] == -1: # 아직 방문 X
                pt[next_q] = q
                depth[next_q] = depth[q] + 1
                queue.append(next_q)

    return pt, depth


def _LCA(x, y):
    if depth_lst[x] < depth_lst[y]:
        x, y = y, x

    while depth_lst[x] != depth_lst[y]:
        x = pt_lst[x]

    while x != y:
        x, y = pt_lst[x], pt_lst[y]

    return x

        
n = int(sys.stdin.readline().rstrip())
conn = _mk_conn(n)
pt_lst, depth_lst = _cr_pt_depth()
m = int(sys.stdin.readline().rstrip())
for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    print(_LCA(a, b))

---

 

⏱️ 시간 복잡도

for _ in range(m) : 질의 만큼 순회 ( 선형 시간 )
	_LCA(x, y) : 공통 조상 찾기 ( 선형 시간 )
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )