[백준] 11437번 : LCA

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

11437번: LCA

해당 문제는 특정 정점2개의 공통 조상을 찾는 문제입니다. 우선 각 정점을 깊이우선탐색으로 각각의 깊이를 구합니다.

구하려는 정점 2개의 공통조상을 찾기위하여 두 정점의 깊이를 맞춰주는데, 자기자신의 조상이 깊이우선탐색을 하면서 기록되었기 때문에 자기자신의 조상을 참조하면서 올라갑니다. 두 정점의 깊이가 일치할경우 같이 조상으로 올라가면서 같은 조상인지 판별 하면 됩니다. 해당문제는 O(n*m) 의시간복잡도를 갖습니다. 조상을 찾아가는 시간복잡도는 O(n)이고 쿼리의 개수가 주어지면 O(m) 이기 때문입니다.

 

import sys
sys.setrecursionlimit(int(1e5))
N = int(input()) # 노드의 개수
graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    a ,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
M = int(input()) # 쌍의 개수

d = [0 for _ in range(N+1)]
c = [False for _ in range(N+1)]
parent = [0 for _ in range(N+1)]

def dfs(rootnode, depth):
    d[rootnode] = depth
    c[rootnode] = True
    for childnode in graph[rootnode]:
        if not c[childnode]:
            parent[childnode] = rootnode
            dfs(childnode, depth+1)
            
            
def lca(a,b):
    # 노드의 깊이를 서로 맞춘다.
    while d[a] != d[b]: # a가 b보다 깊이가 큰경우
        if d[a] > d[b]:
            a = parent[a] # a가 거슬러 올라간다.
        else:
            b = parent[b] # b가 거슬로 올라간다.
            
    while a != b:
        a = parent[a]
        b = parent[b]
        
    return a

dfs(1,0)

for i in range(M):
    a, b = map(int, input().split())
    print(lca(a,b))