[Week 5] FORTRESS self review - profitjean

[profitjean]

FORTRESS self review

1. 해결 시도 과정

현재 성에서 가장 많은 성벽을 넘어야하는 경로는
트리에서 가장 멀리 있는 두 노드를 찾는것과 동일합니다.
현재 노드를 루드로 하는 트리에서 최대 높이를 구하는 재귀함수(max_height)을 구현하고
is_child로 연결관계를 파악하고자 했습니다.

2. 작성한 코드와 설명

def do_enclose(root, child, walls):
    R = walls[root]
    C = walls[child]

    if R[2] > C[2]:
        return (R[2] - C[2]) ** 2 > (R[1]-C[1]) ** 2 + (R[0]-C[0]) ** 2

def is_child(root, child, walls):
    if not do_enclose(root, child, walls):
        return False
    for i in range(len(walls)):
        if i != root and i != child and do_enclose(root, i, walls) and do_enclose(i, child, walls):
            return False
    return True

class Node:
    def __init__(self, root, walls):
        self.children = []
        for i in range(len(walls)):
            if is_child(root, i, walls):
                self.children.append(i)

def max_height(walls):
    longest = 0
    # node를 root로 하는 트리의 최대 높이
    # 이 트리 내에서 노드 간 최대 거리를 구한다
    def find(root):
        node = Node(root, walls)
        heights  = []
        for child in node.childern:
            # 루트 노드 내에서 서브 트리의 높이 저장
            heights.append(find(child))
        # 자식노드가 없다는 것은 자신이 제일 끝, 잎 노드
        if not heights:
            return 0

3. 막힌 점 및 개선 사항

최대 높이를 구하는 과정에서 막혔습니다.

[Queue-ri]

트리의 지름을 구하는 로직은 #173 (comment) 를 참고해주시기 바랍니다!