[Python] 11437 - LCA (골드3)

1. 문제 설명

11437번: LCA

원래 이 문제를 풀려던 건 아니고..LCA2 풀려다가 머리 깨지고 전 단계부터 풀어보기로 했다.

 

---

2. 아이디어

 

LCA가 뭐의 약자인가 했더니 Lowest Common Ancestor(최소 공통 조상)이었다.

나는 좀 무식하게 해결한 거 같다. (그런데 검색해보니까 이게 LCA Algorithm이었다...)

 

트리 정보를 인접 행렬에 담아두고 root 노드부터 dfs를 돌려 깊이 정보와 현재 노드의 부모 노드 정보를 얻어낸다.

그렇게 얻어낸 정보들을 토대로 입력받은 값의 깊이를 확인해 둘의 깊이를 우선 동일하게 맞추어주고,

(여기서 맞추어 준다는 것은 더 깊은 쪽에 있는 노드가 부모 노드로 올라온다.)

여전히 두 값이 다르다면 동시에 부모노드를 따라 올라오다가 값이 같아지는 지점을 찾는다.

---

3. 코드

import sys

sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def dfs(idx, depth):
    visited[idx] = True
    d[idx] = depth

    for node in tree[idx]:
        if visited[node]:
            continue
        parent[node] = idx
        dfs(node, depth+1)

def lca(a, b):
    while d[a] != d[b]: # 깊이 맞추기
        if d[a] > d[b]:
            a = parent[a]
        else:
            b = parent[b]
        
    while a != b: # 같아질 때까지 동시에 부모 노드 탐색
        a = parent[a]
        b = parent[b]

    return a

def solution():
    m = int(input())

    dfs(1, 0) # parent info update

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

if __name__ == "__main__":
    n = int(input())
    parent = [0] * (n+1)    # 각 노드의 부모 노드 info
    d = [0] * (n+1)         # 각 노드까지 깊이
    visited = [0] * (n+1)
    tree = [[] for _ in range(n+1)]

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

    solution()