[BOJ/Python] 11812: K진 트리

gold 3 / 11812: K진 트리

문제 흐름

두 노드 사이의 거리를 구하려면 두 노드의 가장 가까운 조상까지의 각 거리의 합을 구하면 되겠다.
따라서 LCA 알고리즘을 적용시켜야한다.

먼저 문제에서 설명한 K진 트리의 특성에 대해 이해해야한다.
1 ≤ N ≤ 10^15 이고, 1 ≤ K ≤ 1,000 이므로
만약 주어진 정보를 통해 트리를 구성하고 알고리즘을 적용시킨다면 시간과 메모리가 많이 소요될 수 있다.
따라서 K진 트리의 특성을 이용하여 LCA에서 필수적인 부모 노드를 찾는 방법을 수학적으로 알아내야한다!
부모 노드는 위와 같은 패턴을 통해 알 수 있다.

함수는 두개를 만들었다.

⚾️ get_parent

위에서 알아낸 방법을 함수 형태로 만들어놓았다.

⚾️ get_distance

원래라면 binary lifting을 사용하며 올라가는게 효과적이지만,
단순히 깊이가 더 깊은 노드를 끌어올리는 식으로 진행하였다.

코드

# K진 트리
# LCA - Binary Lifting

import sys
input = sys.stdin.readline

def get_parent(k, x):
    if x == 1:
        return 1
    else:
        return (x - 2) // k + 1

def get_distance(k, x, y):
    result = 0
    if k == 1:
        return abs(x - y)
    while x != y:
        if x > y:
            x = get_parent(k, x)
        else:
            y = get_parent(k, y)
        result += 1
    return result

if __name__ == "__main__":
    n, k, q = map(int, input().split())
    for _ in range(q):
        x, y = map(int, input().split())
        answer = get_distance(k, x, y)
        print(answer)