(Python/🥇3)백준알고리즘 11812번 : k 진 트리

 

문제 바로가기 

문제:

각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.

트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.

아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.

노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다.

다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y ≤ N, x ≠ y)

출력:

총 Q개의 줄을 출력한다. 각 줄에는 입력으로 주어진 두 노드 사이의 거리를 출력한다.

 

풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, k, q = map(int, sys.stdin.readline().rstrip().split())


# 부모 노드로 이동
def find(x):
    return (x - 2) // k + 1


def unionfind(a, b):
    distance = 0
    # 숫자가 클수록 뒤에임
    while a != b:
        # 부모로 바꿔줌
        if a > b:
            a = find(a)
        else:
            b = find(b)
        distance += 1
    return distance


for _ in range(q):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    if k == 1:
        print(abs(a - b))
    else:
        print(unionfind(a, b))

 

 

일단 1진 트리인경우 1자로 정렬이 되기 때문에 절댓값을 구해주면 된다.

 

처음에는 parents 배열 선언후 모든 숫자들의 부모를 저장하려고 했지만, 그렇게 되면 배열의 크기가 너무 커지게 되어 비효율이 발생한다.

 

부모의 노드를 인덱스로 생각하여 접근 하고 공식으로 접근하면

 

현재노드 -2 / k진수 + 1 을 때려주면된다.

 

두 노드가 시작값이 되는 순간 리턴한다.