요새 (FORTRESS)

요새 (FORTRESS) :

• 문제 내용 :

@ -16,15 +16,67 @@

• 힌트 :

  • 트리노드의 자료구조를 어떻게 정의하느냐에 따라 코드의 복잡성이 감소함
  • 자주 사용되는 비교 연산은 별도의 함수로 작성하도록 할 것
  • 코드의 복잡성을 줄여야 논리적으로 꼬이지 않음 (트리구축)

• 해결 전략 :

  • 성벽 정보를 통해 트리를 구축한다
  • 두 성벽 정보 A(x1,y1,r1), B(x2,y2,r2)가 주어졌다고 할 때,
    • A-B 거리 =< r1+r2 : A와 B는 포함관계
    • A-B 거리 > r1+r2 : A와 B는 서로 독립적인 관계
    • A-B 거리 < r1+r2 : A와 B는 포함관계
    • A-B 거리 >= r1+r2 : A와 B는 서로 독립적인 관계
  • 위와 같은 계산 방식을 통해 주어진 성벽정보를 토대로 트리를 구축한다
  • 트리가 구축되면 root에서부터 제일 깊이가 깊은 노드까지의 깊이, 즉 트리의 높이가 곧 최대로 성벽을 넘는 횟수가 될 것이다

• 실패 원인 분석 :

  • 문제 해결 로직 자체는 옳으나 코드가 너무 복잡해짐에 따라 내부적으로 작동 로직이 꼬임

  • 예제 입력에서는 정상 작동하나 테스트 케이스 단계에서 오답 발생

  • 두 노드 사이의 거리가 가장 길 때의 거리값을 구하는 함수는 정상 작동한다

  • 트리를 구축하는 방식을 너무 복잡하게 구현한 나머지 노드의 수가 많아지면 논리적으로 꼬이는 것 같다

  • 기존 구현 방식 :

    • TreeNode 자료구조

      • 해당 struct 자료구조 내부에 x,y,r, 자식노드 링크를 갖도록 하였다
      • 이와 같은 방식을 사용하게 되면, 노드간의 비교를 수행하기 위해서는,
        • 노드 내부에 있는 값들(x,y,r)을 비교하는 방법 밖에는 없다
        • 단순히, 정수형 라벨값을 갖도록 하는 방법도 있다
      • 이와 같이 자료구조를 정의하는 것은 코드의 복잡성을 증가시키는 것 같다

    • Tree 구축

      • 트리에 노드를 추가할 때, 노드간의 관계 (포함/독립)를 파악하는 코드를 별도의 함수로 구현 X
        • 코드의 복잡성이 매우 증가함

  • 정답 코드 구현 방식 :

    • TreeNode 자료구조

      • 단순히 자식 노드에 대한 링크를 벡터로 갖고 있는다
      • 노드에 대한 정보(x,y,r)는 전역변수의 배열로 유지한다
        • 이렇게 함으로써 트리노드에 대한 정보를 참조할 때, 단순히 정수 인덱싱을 사용할 수 있다

    • Tree 구축

      • 노드간의 관계(포함/독립)를 파악하는 과정을 별도의 함수로 정의하여 사용

        • 코드의 복잡성이 현저히 줄어듬