아이디어

노드의 양팔 길이가 대칭이다. 재귀적으로 현재 노드에 대해 양쪽 자식이 모두 layout이 적용된 다음 컴팩트하게 자신의 팔 길이를 결정하면 된다.

양쪽 자식들의 팔길이 대칭 맞추기

우선 양쪽 자식은 따로 계산되므로 팔 길이가 깊이별로 달라질 수 있는데, 이를 먼저 맞춰줘야 한다. 예를 들어 왼쪽 자식은 팔길이가 최종 1-2-1으로 결정되었는데, 오른쪽 자식은 1-1-2로 결정되었다면 최종은 깊이별로 더 큰 값으로 맞춰서 1-2-2가 되어야 한다.

자신의 팔길이 결정하기

그런다음 컴팩트한 팔길이를 계산하려면 왼쪽 자식의 오른쪽 프로파일(단계별 가장 큰 x값들)과 오른쪽 자식의 왼쪽 프로파일(단계별 가장 작은 x값들)을 계산하여 각 단계별로 x가 겹치지 않는 팔길이를 계산하면 된다.

결정된 팔길이에 맞춰 양쪽 자식 떨어뜨리기

결정된 팔 길이에 맞춰서 다시 자식들을 translate하는 것도 필요.

코드

재귀를 위한 도움함수 layout3를 호출한다. 이때 기준 x는 마지막에 최소 x 기준점이 1이 되도록 translate해준다. 최소 x를 찾으려면 모든 노드를 탐색해야 한다. (오른쪽 자식의 왼쪽 자식이 최소 x를 가질 수도 있으므로)

void tree_layout3(tree* t) {
    int height = tree_height(t) - 1;
    int* arms = (int*)calloc(height, sizeof(int));
    layout3(t, 0, 1, arms, height);  // arms 버퍼는 최종 결정된 팔길이를 저장한다.
    int minx = tree_fold(t, INT_MAX, tree_xmin);
    tree_translate_x(t, 1-minx);
    free(arms);
}

재귀 layout3 함수는 먼저 왼쪽 오른쪽 자식을 처리한 다음 자식들이 겹치지 않도록 양쪽으로 벌려놓는다. 팔길이 대칭을 맞춰주기 위해 재귀계산을 할때 그 결과로 레벨별 팔길이를 반환한다.(arms 반환인자)

void layout3(tree* t, int x, int y, int* arms, int n) {
    int* armsLeft = (int*)calloc(n-1, sizeof(int));
    int* armsRight = (int*)calloc(n-1, sizeof(int));

    t->x = x;
    t->y = y;

    // 먼저 재귀적으로 팔 길이를 모두 결정한다. 이 때 x에서 시작하므로 겹칠 것이다.
    if (t->left) layout3(t->left, x, y+1, armsLeft, n-1);
    if (t->right) layout3(t->right, x, y+1, armsRight, n-1);

    // 단계별 팔 길이 중 큰 쪽으로 맞춰주기
    for (int i=0; i<n-1; i++) {
        arms[i+1] = max(armsLeft[i], armsRight[i]);
    }

    if (t->left) layout3_setArms(t->left, x, arms+1);
    if (t->right) layout3_setArms(t->right, x, arms+1);

    // 여기부터 armsLeft와 armsRight는 그냥 버퍼로 사용
    for (int i=0; i<n-1; i++) {
        armsLeft[i] = INT_MIN;
        armsRight[i] = INT_MAX;
    }
    // left의 오른쪽 프로파일
    if (t->left) tree_right_profile(t->left, armsLeft);
    // right의 왼쪽 프로파일
    if (t->right) tree_left_profile(t->right, armsRight);

    // 두 프로파일이 겹치지 않도록 현재 노드의 arm을 결정
    int diff = INT_MAX;
    for (int i=0; i<n-1; i++) {
        if (armsRight[i] == INT_MAX || armsLeft[i] == INT_MIN) break;
        diff = min(diff, armsRight[i] - armsLeft[i]);
    }

    int arm = 1 + max(0, -diff / 2);

    if (t->left) tree_translate_x(t->left, -arm);
    if (t->right) tree_translate_x(t->right, arm);
    arms[0] = arm; // 현재 노드 팔길이 저장

    free(armsLeft);
    free(armsRight);
}

팔길이를 재설정하는 함수 setArms

void layout3_setArms(tree* t, int x, int* arms) {
    t->x = x;
    if (t->left) layout3_setArms(t->left, x-*arms, arms+1);
    if (t->right) layout3_setArms(t->right, x+*arms, arms+1);
}

왼쪽/오른쪽 프로파일 구하려면 모든 노드를 돌면서 x좌표의 min혹은 max를 저장하면 된다. profile은 레벨별로 최소값을 저장하기 위한 것이다.

void tree_left_profile(tree* t, int* profile) {
    *profile = min(t->x, *profile);
    if (t->left) tree_left_profile(t->left, profile+1);
    if (t->right) tree_left_profile(t->right, profile+1);
}

void tree_right_profile(tree* t, int* profile) {
    *profile = max(t->x, *profile);
    if (t->left) tree_right_profile(t->left, profile+1);
    if (t->right) tree_right_profile(t->right, profile+1);
}

마지막으로 트리 전체의 최소 x는 right profile의 min값으로 계산할 수도 있겠으나 여기서는 tree_fold 라는 재귀함수를 이용하였다.

int tree_xmin(tree* t, int l, int r) {
    return min(t->x, min(l, r));
}

int tree_fold(tree* t, int z, int (*f)(tree*,int,int)) {
    if (!t) return z;
    int l = tree_fold(t->left, z, f);
    int r = tree_fold(t->right, z, f);
    return f(t, l, r);
}

Ruby

중복(x,y위치)을 갖는 컴팩트 트리를 대칭이 되도록 오른쪽에서 살며시 당기는 방식. 중복지점을 찾고 중복노드 둘의 공통부모를 찾은 뒤 공통부모 포함 우측 노드가 대칭이 되도록 이동/반복. 2번 풀이에서 Node 구조 수정(부모노드 검색 요건) minimize(당기기) 추가.

add = ->par,node do
  par ? (node.y = par.y + 1; node.u = par.id) : (return node)
  chd = node.val < par.val ? par.l : par.r
  chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node)
  par
end

calc_x = ->node,par do
  left_x = par.x + (node == par.l ? -1 : 1) if par
  node.x = (node.l ? node.l.x + 1 : par&.x > 0 ? left_x : 1)
  node.r.x = node.x + 1 if node.r
end

minimize = ->nodes,vst do
  find_dups = -> { nodes.group_by {|e| [e.x, e.y]}.select {|_,v| v.size > 1}.first }
  while dups = find_dups[] do
    d1u, d2u = dups[1].map {|e| parent_id = nodes[e.u] }
    d1u, d2u = nodes[d1u.u], nodes[d2u.u] until d1u == d2u
    d1u.x += 1
    vst.map.with_index {|e,i| e.x += 2 if i > vst.index {|e| e.id == d1u.id } }
  end
end

layout = ->tree_str=gets.chop,visits=[] do
  Node = Struct.new(:id, :val, :x, :y, :l, :r, :u)
  nodes = tree_str.chars.map.with_index {|c,i| Node.new(i, c, 0, 1)}
  btree = nodes.reduce(&add)
  trav = ->node,par=nil do
    trav[node.l, node] if node.l
    calc_x[node, par]
    visits << node
    trav[node.r, node] if node.r
  end
  trav[btree]
  minimize[nodes, visits]
  puts visits.map {|e| [e.val, e.x, e.y].join(" ") }
end

Test

minimized_tree1 = "a 1 4\n" + "c 2 3\n" + "d 2 5\n" + "e 3 4\n" + 
                 "g 4 5\n" + "k 3 2\n" + "m 4 3\n" + "n 5 1\n" + 
                 "p 6 3\n" + "q 7 4\n" + "u 7 2\n"
expect{ layout["nkcmaedgupq"] }.to output(minimized_tree1).to_stdout

Output

cmd > layout.call
nkcmaedgupq
a 1 4 
c 2 3 
d 2 5 
e 3 4 
g 4 5 
k 3 2 
m 4 3 
n 5 1 
p 6 3 
q 7 4 
u 7 2  

일단 적당히 배치한 후에 subtree들이 겹치는지 판단하는 함수를 만들고,

postorder로 순회하면서 안 겹칠 때까지 밀착시키는 게 그나마 간단해 보입니다만... 어렵게 했습니다.

Han Jooyung 님 풀이와 접근 방법은 거의 같습니다. 더 복잡할 뿐..-_-;

.

메인 루틴:

from math import ceil
from itertools import zip_longest

btree = " nkucmp.ae...q....dg.................................."
arm   = [0 for x in btree]
compute_armlength()
def root_x(idx): return 1 if not e_self(idx) else arm[idx] + root_x(idx*2)
inorder(1, root_x(1), 1)

트리와 각 노드의 팔 길이는 그냥 배열처럼 취급했습니다. (이전 레이아웃#2 문제 풀이 참고)

인덱스 검사하기 귀찮아서 길이는 넉넉하게 줬구요.

먼저 compute_armlength()로 각 노드의 팔 길이를 계산합니다.

그리고 왼쪽 팔을 죽 따라가서 루트노드 x좌표를 계산한 후(root_x()함수) inorder로 순회하면서 출력합니다.

일단 노드가 존재하는지 검사하는 함수들과

def e_self(idx): return btree[idx] != '.'
def e_left(idx): return btree[idx*2] != '.'
def e_right(idx): return btree[idx*2+1] != '.'

루트노드부터 시작해서 각 노드의 팔 길이를 더하고 빼서 출력하는 재귀함수입니다.

(루트 위치 안 잡고 한 번에 해 보려다가 상당히 삽질했음...)

def inorder(idx, x, y):
    if not e_self(idx): return
    inorder(idx*2,   x-arm[idx], y+1)
    print(btree[idx], x, y)
    inorder(idx*2+1, x+arm[idx], y+1)

.

그리고 팔 길이를 계산하는 함수:

배열을 거꾸로 스캔하는데, 트리로 치면 BFS의 역순으로 탐색하는 게 됩니다.

배열로 구현한 김에 해 봤는데 postorder로 순회해도 방문 순서는 약간 다르지만 같은 결과가 나옵니다.

즉 어떤 노드 x의 팔 길이를 계산하는 시점에는 x의 자식을 루트로 하는 서브트리들은 계산이 끝난 상태입니다.

자식이 없는 리프노드는 팔 길이가 0,

자식이 하나뿐이면 1이고,

자식이 둘이면 두 서브트리가 겹치지 않는 최소거리를 2로 나눈(팔이 두 개니까) 값이 팔 길이가 됩니다.

def compute_armlength():
    for i in range(len(btree)-1, 0, -1):
        if not e_self(i):  # 노드 없는 자리
            pass        
        elif not e_left(i) and not e_right(i):  # 자식 없음
            arm[i] = 0        
        elif not e_left(i) and e_right(i) or e_left(i) and not e_right(i):  # 자식 하나
            arm[i] = 1    
        else:
            arm[i] = ceil(mindiff(i) / 2)  # 자식 둘

.

compute_armlength()의 마지막 줄에서 호출되는 mindiff()함수와 거기 딸린 함수입니다:

# btree[idx]의 왼쪽 자식과 오른쪽 자식의 (배치 가능한) 최소거리
def mindiff(idx):
    leftsub  = vertical_border(idx*2,   'rightside')  # 왼쪽   자식의 오른쪽 세로경계선
    rightsub = vertical_border(idx*2+1, 'leftside' )  # 오른쪽 자식의 왼쪽   세로경계선

    # 각 depth별 최소 너비
    if len(leftsub) >= len(rightsub):
        mindiff = list(map(lambda x: x[0] - x[1] + 1, zip_longest(leftsub, rightsub, fillvalue=1000000)))
    else:
        mindiff = list(map(lambda x: x[0] - x[1] + 1, zip_longest(leftsub, rightsub, fillvalue=-1000000)))

    return max(mindiff)

mindiff() 함수는

vertical_border() 함수에서 왼쪽 서브트리의 오른쪽 세로경계선과 오른쪽 서브트리의 왼쪽 세로경계선을 받아 와서

두 서브트리가 겹치지 않는 최소 거리를 구합니다.

문제의 입력 예에서 루트 n를 예로 들면,

k를 루트로 하는 서브트리의 왼쪽 세로경계선은 k-m-e-g 이고, k를 기준(0)으로 한 각각의 x좌표 offset은 [0, 1, 0, 1] 입니다.

u을 루트로 하는 서브트리의 오른쪽 경계선은 u-p-q-? 이고, u를 기준(0)으로 x offset이 [0, -1, 0, ?] 입니다,

적당한 수(fillvalue)를 채워서 리스트 길이를 맞추고 같은 depth끼리 차를 구하면

[0-0, 1-(-1), 0-0, 1-?] = [0, 2, 0, ?]

이고, 이중 가장 큰 값이 2입니다.

즉 이 2는 좌우 서브트리가 정확히 겹치는 k와 u의 거리이고, 안 겹쳐야 하니까 1을 더해서 3이 최소 거리가 됩니다.

설명이 장황해서 죄송합니다-_-;

# btree[idx]를 기준(0)으로, 이 서브트리의 왼쪽/오른쪽 세로경계선을 리턴한다.
def vertical_border(idx, dir):
    if not e_self(idx):
        return []

    # 왼쪽/오른쪽 서브트리의 dir방향 세로경계선
    leftsub = vertical_border(idx*2, dir)
    rightsub = vertical_border(idx*2+1, dir)

    # 각 자식을 기준(0)으로 한 좌표이므로, 자신의 팔 길이만큼 이동시킴
    leftsub  = [x - arm[idx] for x in leftsub]
    rightsub = [x + arm[idx] for x in rightsub]

    if dir == 'rightside':
        # leftsub와 rightsub를 합쳐서, depth별로 제일 오른쪽 노드만 추린다.
        bigger  = lambda x : x[0] if x[0] >= x[1] else x[1]
        merged = [bigger(x)  for x in zip_longest(leftsub, rightsub, fillvalue=-100000)]
    else:
        # leftsub와 rightsub를 합쳐서, depth별로 제일 왼쪽 노드만 추린다.
        smaller = lambda x : x[0] if x[0] <= x[1] else x[1]
        merged = [smaller(x) for x in zip_longest(leftsub, rightsub, fillvalue=100000)]

    return [0] + merged

추가) vertical_border는 DP로 하는 게 좋겠네요. 나중에 고치겠습니다.

from string import ascii_letters
from itertools import count

class node:
    class PositionOverlap(Exception): pass

    def __init__(self, name, left = None, right = None):
        self.name = name
        self.left = left
        self.right = right
        self.parent = None
        if self.left:
            self.left.parent = self
        if self.right:
            self.right.parent = self

    def in_order_trav(self, counter = None, queue = {}, depth = 1):
        if counter == None:
            counter = count()
        if self.left:
            self.left.in_order_trav(counter, queue, depth + 1)
        queue[next(counter)] = {depth:self}
        if self.right:
            self.right.in_order_trav(counter, queue, depth + 1)
        return queue

    def even_number_layout(self, width = 0, pos = 0, queue = {}, depth = 1):
        if width == 0:
            width = 2**(self.get_max_depth()-2)
        if self.left:
            self.left.even_number_layout(width/2, pos-width, queue, depth + 1)
        queue[pos] = {depth:self}
        if self.right:
            self.right.even_number_layout(width/2, pos+width, queue, depth + 1)
        return queue

    def symmetry_layout(self, width_map = {}, pos = 0, queue = {}, depth = 1):
        if depth == 1:
            for i in range(1, self.get_max_depth()):
                width_map[i] = 1
            while True:
                try:
                    queue[pos] = {depth:self}
                    if self.left:
                        self.left.symmetry_layout(width_map, pos-width_map[depth], queue, depth + 1)
                    if self.right:
                        self.right.symmetry_layout(width_map, pos+width_map[depth], queue, depth + 1)
                    return queue
                except node.PositionOverlap:
                    queue = {}
        else:
            if pos in queue and depth in queue[pos]:
                sp_d = self.get_shared_parent(queue[pos][depth]).get_depth()
                width_map[sp_d] += 1
                raise node.PositionOverlap
            if pos in queue:
                queue[pos].update({depth:self})
            else:
                queue[pos] = {depth:self}
            if self.left:
                self.left.symmetry_layout(width_map, pos-width_map[depth], queue, depth + 1)
            if self.right:
                self.right.symmetry_layout(width_map, pos+width_map[depth], queue, depth + 1)

    def get_max_depth(self, depth = 1):
        res = depth
        if self.left:
            res = max(res, self.left.get_max_depth(depth + 1))
        if self.right:
            res = max(res, self.right.get_max_depth(depth + 1))
        return res

    def get_depth(self, depth = 1):
        return (self.parent.get_depth(depth+1) if self.parent else depth)

    def get_shared_parent(one, other):
        while one.get_depth() < other.get_depth():
            other = other.parent
            if other == None:
                raise node.NoParent
        while one.get_depth() > other.get_depth():
            one = one.parent
            if one == None:
                raise node.NoParent
        while one != other:
            one = one.parent
            other = other.parent
        return one

    def __str__(self):
        return self.name

class table:
    def __init__(self, queue:{int:{int:node}}):
        self.max_height = max(max(queue[key]) for key in queue)
        self.table = []
        for i in range(self.max_height):
            self.table.append(list(' ' * (int(max(queue) - min(queue))+1)))
        transition = 0-min(queue)
        for x in queue:
            for y in queue[x]:
                self.table[y-1][int(x + transition)] = queue[x][y].name

    def __str__(self):
        res = '   ' + ' '.join('%2d'%i for i in range(1, len(self.table[0])+1)) + '\n'
        for height in range(1, self.max_height+1):
            res += '%2d '%height + ' '.join('%2s'%i for i in self.table[height-1])
            res += '\n'
        return res

def make_tree(_in):
    t_in = list(_in)
    for i in range(len(_in)-1, -1, -1):
        char = t_in[i]
        if char in ascii_letters:
            if _in[i+1] == '(':
                t_in.insert(i+2, ',')
                t_in[i], t_in[i+1] = t_in[i+1], t_in[i]
                t_in.insert(i+2, '\'')
                t_in.insert(i+1, '\'')
                t_in = t_in[:i] + list('node') + t_in[i:]
            else:
                t_in = t_in[:i] + list('node(\'') + [t_in[i], '\')'] + t_in[i+1:]

    str_in = ''.join(t_in)
    str_in = str_in.replace(',,', ', right=')
    str_in = str_in.replace(',)', ')')

    root = eval(str_in)
    return root

if __name__ == '__main__':
    in_1 = 'n(k(c(a,h(g(e,),)),m),u(p(,s(q,)),))'
    print(table(make_tree(in_1).in_order_trav()))
    in_2 = 'n(k(c(a,e(d,g)),m),u(p(,q),))'
    print(table(make_tree(in_2).even_number_layout()))
    in_3 = 'n(k(c(a,e(d,g)),m),u(p(,q),))'
    print(table(make_tree(in_3).symmetry_layout()))

각각의 깊이마다 어느 정도로 펼쳐질 지 결정하는 width_map을 초기화하고, 위치가 중복되는 노드들의 공통 부모를 찾아 벌어지는 폭이 커지도록 증가시키고 중복되지 않을 때까지 반복합니다. 이진트리 레이아웃 #1과 #2의 해법도 들어있어서 좀 깁니다.

파이썬 3.6.2 64