POV

지침

선택한 노드를 기준으로 트리의 부모 관계를 다시 설정해요.

트리는 모든 노드가 연결되어 있지만 순환이 없는 특별한 종류의 그래프예요. 즉, 어떤 두 노드를 골라도 한 노드에서 다른 노드로 가는 경로가 정확히 하나만 있어요.

이 연습 문제는 트리를 다른 관점에서 바라보도록 방향을 바꾸는 것에 관한 거예요. 예를 들어 가계도는 보통 조상의 관점에서 표현해요:

    +------0------+
    |      |      |
  +-1-+  +-2-+  +-3-+
  |   |  |   |  |   |
  4   5  6   7  8   9

하지만 트리에는 원래부터 정해진 방향이라는 게 없어요. 같은 정보를 트리의 다른 어떤 노드의 관점에서도 표현할 수 있어요. 그 노드를 루트로 끌어올리고 그 관계들도 함께 끌고 가면 돼요. 그래서 같은 트리를 6의 관점에서 보면 이렇게 돼요:

        6
        |
  +-----2-----+
  |           |
  7     +-----0-----+
        |           |
      +-1-+       +-3-+
      |   |       |   |
      4   5       8   9

이렇게 하면 두 노드 사이의 경로를 더 간단하게 설명할 수 있어요. 예를 들어 6-9 경로는 (첫 번째 트리에서는 루트까지 올라갔다가 다른 리프 노드로 내려가죠) 6-2-0-3-9 경로를 따라간다는 걸 알 수 있어요.

이 연습 문제에서는 입력으로 주어진 트리를 노드 하나의 관점에서 다시 방향을 바꿔요.

구현 참고 사항

테스트 프로그램은 가변 인자 New 함수를 반복해서 적용해 트리를 만들어요. 예를 들어, 다음 문은

tree := New("a",New("b"),New("c",New("d")))

다음 트리를 만들어요:

      "a"
       |
    -------
    |     |
   "b"   "c"
          |
         "d"

테스트 트리에는 중복된 값이 없다고 가정해도 돼요.

Value와 Children 메서드는 테스트 프로그램이 트리를 분해할 때 사용해요.

연습 문제에서 흥미로운 부분을 시작하기 전에 기본적인 트리 구성과 분해가 먼저 동작해야 하므로, 처음 세 개의 테스트에서 따로 테스트해요.

FromPov와 PathTo 메서드가 이 연습 문제의 흥미로운 부분이에요.

FromPov 메서드는 값으로 트리의 노드를 지정하는 문자열 인자 from을 받아요. 값 from이 루트에 있는 트리를 반환해야 해요. 원래 트리를 수정해서 그대로 반환해도 되고, 새 트리를 만들어 반환해도 돼요. 새 트리를 반환한다면 원래 트리를 소비하거나 파괴해도 괜찮아요. 물론 원래 트리를 그대로 두면 더 좋아요.

PathTo 메서드는 값으로 트리의 두 노드를 지정하는 두 개의 문자열 인자 from과 to를 받아요. 첫 번째 노드에서 두 번째 노드까지 트리에서 가장 짧은 경로를 반환해야 해요.

---

출처

4clojure의 연습 문제를 각색한 것이에요.