지침
선택한 노드를 기준으로 트리의 부모 관계를 다시 설정해요.
트리는 모든 노드가 연결되어 있지만 순환이 없는 특별한 종류의 그래프예요.
즉, 어떤 두 노드를 골라도 한 노드에서 다른 노드로 가는 경로가 정확히 하나만 있어요.
이 연습 문제는 트리를 다른 관점에서 바라보도록 방향을 바꾸는 것에 관한 거예요.
예를 들어 가계도는 보통 조상의 관점에서 표현해요:
+------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 경로를 따라간다는 걸 알 수 있어요.
이 연습 문제에서는 입력으로 주어진 트리를 노드 하나의 관점에서 다시 방향을 바꿔요.
구현 참고 사항
Tree 객체에는 두 가지 속성이 있어요:
-
String label
-
List<Tree> children
테스트 프로그램은 Tree.of 빌더 함수를 반복해서 적용해 트리를 만들어요. 예를 들어, 다음 문은
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
다음과 같은 트리를 만들어요:
"a"
|
-------
| |
"b" "c"
|
"d"
테스트 트리에는 중복된 값이 없다고 가정해도 돼요.
FromPov와 PathTo 메서드가 이 연습 문제에서 흥미로운 부분이에요.
FromPov 메서드는 트리의 노드를 값으로 지정하는 문자열 인자 from을 받아요. 루트에 from 값을 가진 트리를 반환해야 해요. 원래 트리를 수정해서 반환해도 되고, 새 트리를 만들어서 반환해도 돼요. 새 트리를 반환한다면 원래 트리를 소비하거나 파괴해도 괜찮아요. 물론 원래 트리를 그대로 두면 더 좋아요.
PathTo 메서드는 트리의 두 노드를 값으로 지정하는 두 개의 문자열 인자 from과 to를 받아요. 첫 번째 노드에서 두 번째 노드로 가는 트리 안의 최단 경로를 반환해야 해요.
예외 메시지
때로는 예외를 던져야 할 때가 있어요. 이때 오류의 원인이 무엇인지 알려 주는 의미 있는 오류 메시지를 항상 함께 넣어야 해요. 그러면 코드를 더 읽기 쉽게 만들고 디버깅에 큰 도움이 돼요.
이 연습 문제에서는 Tree() 클래스에 재정향할 수 없는 트리가 전달되거나 start node와 end node 사이의 경로를 찾을 수 없을 때, throw 키워드를 사용해 여러 개의 UnsupportedOperationException을 "던져야" 해요. throw로 exception을 던지고 그와 함께 메시지를 포함해야만 테스트를 통과할 수 있어요.
메시지와 함께 UnsupportedOperationException을 던지려면, 메시지를 exception 타입의 인자로 작성해요:
// when a tree cannot be oriented to a new node POV
throw new UnsupportedOperationException("Tree could not be reoriented");
// when a path cannot be found between a start and end node on the tree.
throw new UnsupportedOperationException("No path found");
