🧚‍♂️알고리즘🧚‍♂️ - 🌴 - 최소 공통 조상 (LCA 알고리즘)

🌴 최소 공통 조상🌴

임의의 두 노드에서  처음 공통으로 만나게 되는 부모 노드를 지칭하는 말

LCA 알고리즘 이용

 

🌴일반적인 최소 공통 조상 구하기(높이가 크지 않음) 

- 깊이 맞춰 주기 (깊이 알기-DFS,BFS 등 이용)

- 동시에 부모 노드로 올라가면서 같은 노드에 도착할 때가지 반복하기

 

🌴빠른 최소 공통 조상 구하기(높이가 크지 않음)

- 부모 노드 저장 리스트 만들기

부모 노드 리스트

p[k][n] : n번 노드의 2^k번째 부모의 노드 번호

부모 노드 리스트 점화식

p[k][n] = p[k-1][p[k-1][n]]

 

- 선택된 두 노드의 깊이 맞추기

2^k  단위로 이동하면서 맞추기

 

- 최소 공통 조상 찾기

2^k  단위로 이동하면서 찾기

---

골드 3

11437번: LCA

LCA 알고리즘 :최소 공통 조상을 찾는 알고리즘

from sys import stdin
from collections import deque

N = int(stdin.readline()) #수 개수

tree = [[] for _ in range(N+1)] # 트리 인접 리스트 구현
for _ in range(N-1):
    s,e = map(int, stdin.readline().split()) 
    tree[s].append(e)
    tree[e].append(s)

tree_depth = [0]*(N+1) # 트리 깊이 리스트
tree_parent = [0]*(N+1) # 트리 부모 리스트
visited = [False]*(N+1) #방문리스트

def BFS(v): #깊이 확인용 탐색
    my_queue = deque()
    my_queue.append(v)
    visited[v] = True
    
    depth = 1 #현재 깊이 변수
    now_depth_size = 1 # 현재 해당 깊이 노드 수
    now_depth_checked_node = 0 # 현재 체크한 해당 깊이 노드 수

    while (my_queue):
        now_node = my_queue.popleft()
        for cha in tree[now_node]:
            if not visited[cha]:
                visited[cha] = True
                my_queue.append(cha)

                tree_parent[cha] = now_node # 부모 노드 저장
                tree_depth[cha] = depth # 깊이 저장
        #깊이 갱신 체크
        now_depth_checked_node += 1 # 하나 노드 체크 완료
        if now_depth_size == now_depth_checked_node : # 현재 깊이 노드들 전부 체크 완료
            depth += 1
            now_depth_size = len(my_queue) #현재 큐에 있는 애들이 이전 노드 자식들,즉 다음 깊이 노드들
            now_depth_checked_node = 0

BFS(1) # 깊이/부모노드 알아내기

#최소공통조상 찾기(LCA 알고리즘)
def executeLCA(a,b):
    if tree_depth[a] < tree_depth[b]: #a깊이가 더 깊게
        temp = a
        a = b
        b = temp

    while (tree_depth[a] != tree_depth[b]): #깊이 맞추기
        a = tree_parent[a]
    
    while a != b: # 둘이 같은 값이 될 때까지(공통 조상 만날 때까지)
        a = tree_parent[a] # 한단계씩 올라가기
        b = tree_parent[b]
    
    return a

#결과
M = int(stdin.readline()) # 질의 개수

for _ in range(M):
    a, b = map(int, stdin.readline().split()) 
    print(executeLCA(a,b))

음 근데 파이썬 시간초과   C++ 공부 열심히 해야지

---

플래티넘 5

11438번: LCA 2

노드/질의의 크기 짱큼

기존 LCA보다 더 빠른 "제곱수 형태를 이용한 최소 공통 조상 구하기" 방식 이용

 

- 점화식을 이용해 부모 노드 리스트를 구함 

2^0번째,2^1번째,2^2번째...부모 리스트 : 2의 제곱수 부모까지 단번에 확인 가능

p[k][n] = p[k-1][p[k-1][n]]

- 2^k 만큼 빠르게 이동시킴(한 칸씩이 아니라)

import sys
from collections import deque

N = int(sys.stdin.readline()) #수 개수

tree = [[] for _ in range(N+1)] # 트리 인접 리스트 구현
for _ in range(N-1):
    s,e = map(int, sys.stdin.readline().split()) 
    tree[s].append(e)
    tree[e].append(s)

tree_depth = [0]*(N+1) # 트리 깊이 리스트
visited = [False]*(N+1) #방문리스트

#최대 가능 깊이 구하기!!
temp = 1
k_max = 0
while(temp <= N):
    temp *= 2 # 또는 쉬프트 연산자 <<=1
    k_max += 1

# 특별한 부모 리스트(2의 제곱수 부모들)!!!
tree_parent = [[0 for _ in range(N+1)] for _ in range(k_max+1)]

def BFS(v): #깊이 확인용 탐색
    my_queue = deque()
    my_queue.append(v)
    visited[v] = True
    
    depth = 1 #현재 깊이 변수
    now_depth_size = 1 # 현재 해당 깊이 노드 수
    now_depth_checked_node = 0 # 현재 체크한 해당 깊이 노드 수

    while (my_queue):
        now_node = my_queue.popleft()
        for cha in tree[now_node]:
            if not visited[cha]:
                visited[cha] = True
                my_queue.append(cha)

                tree_parent[0][cha] = now_node # 부모 노드 저장
                tree_depth[cha] = depth # 깊이 저장
        #깊이 갱신 체크
        now_depth_checked_node += 1 # 하나 노드 체크 완료
        if now_depth_size == now_depth_checked_node : # 현재 깊이 노드들 전부 체크 완료
            depth += 1
            now_depth_size = len(my_queue) #현재 큐에 있는 애들이 이전 노드 자식들,즉 다음 깊이 노드들
            now_depth_checked_node = 0

BFS(1) # 깊이/부모노드 알아내기

#2의 제곱수 부모들 구하기!!
for k in range(1, k_max+1):
    for n in range(1,N+1):
        tree_parent[k][n] = tree_parent[k-1][tree_parent[k-1][n]] #점화식

#최소공통조상 찾기(LCA 알고리즘) 변형
def executeLCA(a,b):
    if tree_depth[a] < tree_depth[b]: # a 깊이가 더 깊게
        temp = a
        a = b
        b = temp

    for k in range(k_max,-1,-1): #깊이 맞추기 (빠르게)
        if pow(2,k) <= tree_depth[a] - tree_depth[b] and tree_depth[b] <= tree_depth[tree_parent[k][a]]:
            a = tree_parent[k][a]
    
    for k in range(k_max,-1,-1): # 조상 찾기 (빠르게)
        if a == b:
            return a
        if tree_parent[k][a] != tree_parent[k][b]:
            a = tree_parent[k][a]
            b = tree_parent[k][b]

    return tree_parent[0][a]

#결과
M = int(sys.stdin.readline()) # 질의 개수

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split()) 
    print(executeLCA(a,b))

오 잠깐 변형 LCA 함수 이해 안돼

그렇지만 2시 넘었으니 내일 보자고

내일 9시ㅐ 수강신청이야