René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"[Week 5] FORTRESS self review - profitjean","articleBody":"# FORTRESS self review ![](https://img.shields.io/badge/-WA-%23e00000)\r\n\r\n## 1. 해결 시도 과정\r\n현재 성에서 가장 많은 성벽을 넘어야하는 경로는 \r\n트리에서 가장 멀리 있는 두 노드를 찾는것과 동일합니다.\r\n현재 노드를 루드로 하는 트리에서 최대 높이를 구하는 재귀함수(max_height)을 구현하고\r\nis_child로 연결관계를 파악하고자 했습니다.\r\n\r\n## 2. 작성한 코드와 설명\r\n```py\r\ndef do_enclose(root, child, walls):\r\n    R = walls[root]\r\n    C = walls[child]\r\n\r\n    if R[2] \u003e C[2]:\r\n        return (R[2] - C[2]) ** 2 \u003e (R[1]-C[1]) ** 2 + (R[0]-C[0]) ** 2\r\n```\r\n```py\r\ndef is_child(root, child, walls):\r\n    if not do_enclose(root, child, walls):\r\n        return False\r\n    for i in range(len(walls)):\r\n        if i != root and i != child and do_enclose(root, i, walls) and do_enclose(i, child, walls):\r\n            return False\r\n    return True\r\n```\r\n```py\r\nclass Node:\r\n    def __init__(self, root, walls):\r\n        self.children = []\r\n        for i in range(len(walls)):\r\n            if is_child(root, i, walls):\r\n                self.children.append(i)\r\n\r\ndef max_height(walls):\r\n    longest = 0\r\n    # node를 root로 하는 트리의 최대 높이\r\n    # 이 트리 내에서 노드 간 최대 거리를 구한다\r\n    def find(root):\r\n        node = Node(root, walls)\r\n        heights  = []\r\n        for child in node.childern:\r\n            # 루트 노드 내에서 서브 트리의 높이 저장\r\n            heights.append(find(child))\r\n        # 자식노드가 없다는 것은 자신이 제일 끝, 잎 노드\r\n        if not heights:\r\n            return 0\r\n```\r\n## 3. 막힌 점 및 개선 사항\r\n최대 높이를 구하는 과정에서 막혔습니다.","author":{"url":"https://github.com/profitjean","@type":"Person","name":"profitjean"},"datePublished":"2022-02-24T10:38:47.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":1},"url":"https://github.com/177/Advanced-Algorithm-Study/issues/177"}