[11437] 최소 공통 조상 (트리, 일반 LCA)

11437번: LCA

 

분석

최소 공통 조상

• 임의의 두 노드를 선택 했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드(lowest common acestor)

최소 공통 조상 구하기

• 루트 노드에서 탐색을 시작해각 노드의 부모 노드와 깊이 저장 (DFS/BFS로 탐색)
• 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춤. 두 노드가 같으면 해당 노드가 공통 조상이므로 탐색 중단
• 깊이가 같은 상태에서 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복, 이 때 처음 만나는 노드가 최소 공통 조상

 

풀이

import sys
input = sys.stdin.readline

n = int(input())  # 수의 개수
tree = [[] for _ in range(n+1)]  # 트리 데이터 저장
for _ in range(0, n-1):
    s, e = map(int, input().split())
    tree[s].append(e)
    tree[e].append(s)

depth=[0]*(n+1)  # 노드 깊이 리스트
parent = [0]*(n+1) # 노드 조상 리스트
visited=[False]*(n+1)  # 방문체크 저장 리스트

def BFS(node):
    queue = [node]
    visited[node] = True  # 현재 노드 방문 기록
    while queue:
        # 큐에서 노드 데이터 가져오기
        now_node = queue.pop(0)
        for next in tree[now_node]:  # 현재 노드와 연결된 노드 탐색
            if not visited[next]:
                visited[next] = True
                queue.append(next)  # 큐에 데이터 삽입
                parent[next] = now_node  # 부모 노드 저장
                depth[next] = depth[now_node] + 1  # 노드 depth 저장

BFS(1) # 깊이와 부모 노드 저장

def LCA(a, b):
    if depth[a] < depth[b]: # a노드가 더 작으면 swap, 더 깊은 depth가 a가 되도록
        temp =a
        a=b
        b=temp
    while depth[a]!=depth[b]:  # depth 맞추기
        a=parent[a]
    while a!=b: # 공통조상찾기
        a=parent[a]
        b=parent[b]

    return a

m=int(input())
mydict = dict()
for _ in range(m):
    a, b = map(int, input().split())
    if not mydict.get((a, b), 0): #같은 질문일 경우 재계산을 하지 않기 위해 딕셔너리 자료형 사용
        mydict[(a, b)] = mydict[(b, a)] = LCA(a, b)
    print(mydict.get((a, b)))

 

 

 

최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과)