[ 백준 ][ 골드3 ] 11812번 - K진 트리 ( 파이썬 )

링크 : https://www.acmicpc.net/problem/11812

11812번: K진 트리

문제

---

코드

---

- 맨 처음 제출한 코드

import sys
input = sys.stdin.readline

def getDepth(node):
    i,cnt = 0,0
    while 1:
        cnt += k**i
        if cnt >= node:
            return i
        i += 1

def getParent(node):
    return (node-2)//k + 1

def LCA(x,y):
    if getDepth(x) != getDepth(y):
        while getDepth(x) != getDepth(y):
            if getDepth(x) > getDepth(y):
                x = getParent(x)
                continue
            y = getParent(y)
    while x != y:
        x = getParent(x)
        y = getParent(y)
    return x

n,k,q = map(int,input().split())
for _ in range(q):
    x,y = map(int,input().split())
    if k == 1:
        print(abs(x-y))
        continue
    print(getDepth(x) + getDepth(y) - 2 * getDepth(LCA(x,y)))

 

- 3등이 되어버린 코드

import sys
input = sys.stdin.readline

def getParent(node):
    return (node-2)//k + 1

def LCA(x,y):
    d = 0
    while x != y:
        if x > y:
            x = getParent(x)
        else:
            y = getParent(y)
        d += 1
    return d

n,k,q = map(int,input().split())
for _ in range(q):
    x,y = map(int,input().split())
    if k == 1:
        print(abs(x-y))
        continue
    print(LCA(x,y))

풀이

---

기존의 LCA(최소공통조상알고리즘)의 변형이라고 볼 수 있다.

 

기존에는 이진트리에서 부모와 자식간의 관계라 2n, 2n-1임을 이용해서 부모노드를 찾았다면

이번 문제에서는 k진트리이기 때문에 부모 노드를 찾는 다른 방법이 필요했다.

 

다행히도 문제에서 "적은 에너지" 방법을 설명해줌으로써 부모노드를 찾는 방법을 제시해준다.

최종적으로 만들어질 부모노드 공식은 (node-2)//k+1이다.

 

| LCA | - 맨 처음 제출한 코드

• 기존의 LCA를 최대한 이용한 코드이다.
• 두 노드의 깊이를 비교하여 깊이가 같을 때까지 맞춰주고 부모노드를 향해 같이 올라간다.
• 부모노드를 만나면 부모노드를 리턴한다.
• K==1이라면 일렬로 이루어진 트리구조이기 때문에 작은 수가 반드시 큰 수의 부모이다.
• 따라서 절대값(큰 값 - 작은 값)을 출력한다.

 

| LCA | - 3등이 되어버린 코드

• 기존의 LCA를 조금 이용하고 변형한 코드이다.
• 위의 코드와의 차이점은 큰 수는 반드시 작은 수보다 깊이가 작거나 같다는 것을 깨달은 것이다.
• 따라서 깊이를 따로 구하지 않고 두 수가 같을 때까지 계속해서 부모노드로 바꿔주었다.
• 또 부모노드를 바꾼다는 것이 바로 거리가 늘어나는 것이므로 따로 깊이계산으로 정답을 구하지 않고 LCA안에서 해결했다.