EDOC 2023-W 7회차 과제 (최소 공통 조상)

09-5. 최소 공통 조상

 

074. LCA (백준 11437번)

 

https://www.acmicpc.net/problem/11437

 

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

n = int(input())
tree = [[] for _ in range(n+1)]
depth = [0] * (n+1)
parent = [0] * (n+1)
visited = [False] * (n+1)

def bfs(node):
    que = deque()
    que.append(node)
    visited[node] = True
    level = 1
    size = 1
    cnt = 0
    while que:
        now = que.popleft()
        for nxt in tree[now]:
            if not visited[nxt]:
                visited[nxt] = True
                que.append(nxt)
                parent[nxt] = now
                depth[nxt] = level
        cnt += 1
        if cnt == size:
            cnt = 0
            size = len(que)
            level += 1

def LCA(a, b):
    if depth[a] < depth[b]:
        tmp = a
        a = b
        b = tmp
    
    while depth[a] != depth[b]:
        a = parent[a]
    
    while a != b:
        a = parent[a]
        b = parent[b]
    
    return a

for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

bfs(1)

m = int(input())
for _ in range(m):
    a, b = map(int, input().split())
    print(LCA(a, b))

Python으로 제출하면 시간 초과가 뜬다. 교재에는 print = sys.stdout.write 를 썼길래 이렇게 하면 더 시간이 단축되나 해서 교재대로 수정 후 제출해도 똑같이 시간 초과가 뜬다. PyPy로 제출하니 괜찮았다. (정답)

 

---

 

075. LCA 2 (백준 11438번)

 

https://www.acmicpc.net/problem/11438

 

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

n = int(input())
tree = [[] for _ in range(n+1)]
depth = [0] * (n+1)
visited = [False] * (n+1)
kmax = math.floor(math.log2(n)) + 1

parent = [[0 for j in range(n+1)] for i in range(kmax+1)]

def bfs(node):
    que = deque()
    que.append(node)
    visited[node] = True
    level = 1
    size = 1
    cnt = 0
    while que:
        now = que.popleft()
        for nxt in tree[now]:
            if not visited[nxt]:
                visited[nxt] = True
                que.append(nxt)
                parent[0][nxt] = now
                depth[nxt] = level
        cnt += 1
        if cnt == size:
            cnt = 0
            size = len(que)
            level += 1

def LCA(a, b):
    if depth[a] > depth[b]:
        tmp = a
        a = b
        b = tmp
    
    for k in range(kmax, -1, -1):
        if pow(2, k) <= depth[b] - depth[a]:
            if depth[a] <= depth[parent[k][b]]:
                b = parent[k][b]
    
    for k in range(kmax, -1, -1):
        if a == b:
            break
        if parent[k][a] != parent[k][b]:
            a = parent[k][a]
            b = parent[k][b]

    res = a
    if a != b:
        res = parent[0][res]
    return res

for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

bfs(1)

for k in range(1, kmax+1):
    for n in range(1, n+1):
        parent[k][n] = parent[k-1][parent[k-1][n]]

m = int(input())
for _ in range(m):
    a, b = map(int, input().split())
    print(LCA(a, b))

플래... 너무 어려워서 그냥 거의 교재에 있는걸 그대로 쳐서 풀었다... 제대로 이해하려면 이에 대해서 더 찾아봐야 될 것 같다. (정답)