[pyhon] algospot FORTRESS

문제

-> 문제 링크 : https://algospot.com/judge/problem/read/FORTRESS

algospot.com :: FORTRESS

 

문제풀이

외벽이 아닌 성벽은 항상 자신보다 큰 하나의 성벽 안에 포함되어 있다.

각 성벽은 계층적 구조를 갖고 있으며 이는 트리로 표현이 가능하다.

 

외벽은 겹치지 않기 떄문에 항상 반지름이 작은 외벽이 더 큰 반지름을 갖는 외벽을 포함할 수 없다.

그렇기에 트리로 표현한다면 반지름이 큰 외벽이 항상 부모 노드일 수밖에 없다.

반지름이 큰 외벽부터 넣는다면 하나의 외벽이 삽입되는 순간에 현재 트리에 존재하는 외벽들 안에 포함되어 있는지만 검사하면 된다.

 

외벽이 트리로 표현된다면 현재 성에서 가장 많은 성벽을 넘어야 하는 경로는 트리에서 가장 멀리 있는 두 노드를 찾는 문제가 된다.

이때 두 노드의 최대 거리는 최대 높이를 가진 두 서브트리의 높이 합이 된다.

현재 노드를 루트로 하는 트리에서 최대 높이를 구하는 재귀 함수를 구현한 뒤 이를 이용해 트리의 최대 거리를 계산해주면 된다.

 

주의해야 할 점은 최대 높이가 항상 루트에서 나오지는 않는다. 그렇기에 두 서브 트리의 높이 합을 구하는 코드는 모든 노드에 재귀적으로 실행되어야 하고, 그중 최댓값을 구해야 한다.

코드

import sys
import math

class Node :
    def __init__(self, x,y,r):
        self.x = x
        self.y = y
        self.r = r
        self.child = []

    def isIn(self, node):

        distance = math.sqrt( (self.x - node.x)**2 + (self.y - node.y)**2 )

        if distance < node.r :
            return True
        else :
            return False

    def addChild(self, node):
        self.child.append(node)


class Tree :

    def __init__(self) :
        self.root = None
        self.distance = 0


    def add(self, node) :
        if self.root :
            self.add_rec(self.root, node)
        else :
            self.root = node


    def add_rec(self, root, node):

        for child in root.child :
            if node.isIn(child) :
                self.add_rec(child, node)
                return True

        root.addChild(node)


    def maxDistance(self):
        self.maxDepth(self.root)


    def maxDepth(self, node):
        # node를 root로 하는 트리의 최대 높이,
        # 이 트리 안에서 노드간 최대 거리를 구함

        if not node.child :
            return 1

        depths = []
        maxDepth = 1
        for child in node.child :
            sub_depth = self.maxDepth(child)
            maxDepth = max(maxDepth, sub_depth+1)

            depths.append(sub_depth)

        if len(depths) > 1 :
            depths = sorted(depths, reverse=True)
            self.distance = max(self.distance, depths[0] + depths[1])
        else :
            self.distance = max(self.distance, depths[0])

        return maxDepth


T = int(sys.stdin.readline().rstrip())

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip())

    fortress = []
    for _ in range(N) :
        x,y,r = map(int, sys.stdin.readline().rstrip().split(" "))
        fortress.append( (x,y,r) )


    fortress = sorted(fortress, key = lambda x: -x[2])
    tree = Tree()
    for x,y,r in fortress :
        tree.add( Node(x,y,r) )

    tree.maxDistance()
    print(tree.distance)

초기 접근 방식과 오답의 원인

최댓값은 루트의 양쪽 서브트리 높이의 합이라고 생각하여 문제를 풀지 못했다.

서브 트리에서도 최대 거리가 발생할 수 있다는 점을 주의해야 한다.

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.