Algorithm // Lowest Common Ancestor ( LCA )

LCA란?

• 사이클이 없고 루트가 존재하는 트리에 대해 두 정점의 가장 가까운 조상을 의미한다.

예를 들어 해당 트리에서 11과 2의 LCA는 7이다.

어떻게 찾을까?

좀 느린 방식 [ O(N) 시간복잡도 ]

1. 일단 그래프에 DFS를 돌려 모든 정점의 깊이를 구한다.
2. 두 정점의 깊이를 비교해 깊이가 깊은쪽을 parent로 올려 동일하게 맞춘다.
   Ex. 위 그래프에서 2와 11 에 대해 찾을땐, 11을 parent인 6으로 바꿔 높이를 맞춘다
3. 만약 여기서 두 정점의 값이 같아지면 거기가 LCA
   만약 같아지지 않는다면 4로 넘어간다.
4. 두 정점에서 한칸씩 천천히 parent로 넘어가면서 정점이 같아질때까지 반복한다.
5. 두 정점의 값이 같아지면 그것이 곧 LCA이다.

이 방식은 왜 큰 값에서 쓰기 어려울까?

• 그래프가 균등하게 분포하여 높이가 LogN에 가까울 경우 괜찮지만 만약 그래프가 한줄로 쭉 이어지는 형태일시 O(N)의 최악 시간복잡도를 가지게 된다.

속도가 괜찮은 방식 [ O(LogN) 시간복잡도 ]

• 여기서는 독특한 자료구조가 하나 추가된다.
  parent[n][a] 와 같이 표현하는데 이것은
  a번 노드의 $2^n$ 번째 부모 노드 를 의미한다.

1. 일단 그래프에 BFS를 돌려 모든 정점의 깊이를 구한다. 이때 parent 자료구조의 값도 정한다.

    def __init__(self, edges: List[List[int]]):
        self.graph = defaultdict(list)
        self.SIZE = 0
        for s, e in edges:
            self.graph[s].append(e)
            self.graph[e].append(s)
            self.SIZE = max(self.SIZE, s, e)

        self.depth = [0] * (self.SIZE + 1)
        self.parent = [[0] * (self.SIZE + 1) for _ in range(LOG)]

        self.build()

    def build(self, root: int = 1):
        visited = [False] * (self.SIZE + 1)
        q = deque([(root, 1)])

        # build depth
        while q:
            n, d = q.popleft()
            self.depth[n] = d
            visited[n] = True

            for dst in self.graph[n]:
                if visited[dst]:
                    continue
                self.parent[0][dst] = n
                q.append((dst, d + 1))

        # build parent
        for k in range(1, LOG):
            for node in range(self.SIZE + 1):
                if self.depth[node] == 0:
                    continue
                mid = self.parent[k - 1][node]
                self.parent[k][node] = self.parent[k - 1][mid]

2. 두 정점의 높이를 동일하게 하는 방법

• 먼저 두 높이의 차이를 구한다.
• 그 뒤에 2진법 연산을 고려해 어떤 n만큼 점프할지를 정하고 그만큼 점프해 나간다.
• 알아서 맞춰진다.
• 즉 Log(N)에 2번 절차를 끝냈다.

        if self.depth[a] < self.depth[b]:
            a, b = b, a

        diff = self.depth[a] - self.depth[b]

        if diff > 0:
            for level in range(LOG):
                if diff & (1 << level):
                    a = self.parent[level][a]

3. 같아지면 리턴

4. 같지 않으면 같아지는 점 직전까지 이동한다.

        for level in range(LOG - 1, -1, -1):
            if self.parent[level][a] != self.parent[level][b]:
                a = self.parent[level][a]
                b = self.parent[level][b]

• 여기서 중요한 부분은 절대 같아지기 직전까지 이동한다는것이다.
• 여기선 큰 값부터 작은값까지 이동해 파인 튜닝한다고 생각하고 접근한다.

5. 찾은 노드의 parent가 곧 LCA가 된다!

코드

LOG = 21


class LCA:
    def __init__(self, edges: List[List[int]]):
        self.graph = defaultdict(list)
        self.SIZE = 0
        for s, e in edges:
            self.graph[s].append(e)
            self.graph[e].append(s)
            self.SIZE = max(self.SIZE, s, e)

        self.depth = [0] * (self.SIZE + 1)
        self.parent = [[0] * (self.SIZE + 1) for _ in range(LOG)]

        self.build()

    def build(self, root: int = 1):
        visited = [False] * (self.SIZE + 1)
        q = deque([(root, 1)])

        # build depth
        while q:
            n, d = q.popleft()
            self.depth[n] = d
            visited[n] = True

            for dst in self.graph[n]:
                if visited[dst]:
                    continue
                self.parent[0][dst] = n
                q.append((dst, d + 1))

        # build parent
        for k in range(1, LOG):
            for node in range(self.SIZE + 1):
                if self.depth[node] == 0:
                    continue
                mid = self.parent[k - 1][node]
                self.parent[k][node] = self.parent[k - 1][mid]

    def query(self, a: int, b: int) -> int:
        if self.depth[a] < self.depth[b]:
            a, b = b, a

        diff = self.depth[a] - self.depth[b]

        if diff > 0:
            for level in range(LOG):
                if diff & (1 << level):
                    a = self.parent[level][a]

        if a == b:
            return a

        for level in range(LOG - 1, -1, -1):
            if self.parent[level][a] != self.parent[level][b]:
                a = self.parent[level][a]
                b = self.parent[level][b]

        return self.parent[0][a]

• LOG의 값은 노드의 값중 최대가 되는것을 고려하여 적절히 구하면 속도가 조금이나마 더 빠를것이다.