비록 저는 시간 초과로 1~5, 8, 21, 26만 통과하였지만, 사소하게 자명한 부분을 정리해 봅니다.

용어정의

• Leaf: 연결이 1개 혹은 2개인 노드입니다.
• Split: 연결이 3개 이상인 노드입니다.

자명한 내용

1. Split이 없는 경우 I자로 모든 노드가 연결되어 있습니다. return (t의 행의 개수 + 1)
2. Split 노드에서 Leaf 노드로 연결된 경우는 최종적으로 U자 형태로 되돌아오게 됩니다. 따라서 예시 1 [[5,1],[2,5],[3,5],[3,6],[2,4],[4,0]]에서 5번 Split 노드는 [1], [3,6,3], [2,4,0,4,2]이라는 선택지를 미리 알 수 있습니다. 3: 연속되서 연결된 Leaf전체에 대하여 방문 횟수를 구할 필요없습니다. Split에서 Leaf의 경우는 방문한적 없는 Leaf만 탐색하면 됩니다.
3. Split노드에서 Leaf를 선택할때 깊이가 가장 깊은것부터 3개만 고려하면 됩니다. 3개의 최장 Leaf + 다른 Split으로 연결되는 경우만 탐색하면 됩니다. (예시 2 [[2,5],[2,0],[3,2],[4,2],[2,1]]의 경우 2번 노드에서 정리하면 4개 노드만 남게 됩니다.)
4. 전체 탐색을 한다면, Leaf에서 시작하는게 ㅅ자로 구성이 되기에 가장 많은 점을 방문합니다. Split에서 시작하는 경우를 제외 할 수 있습니다. 따라서 Split에 대하여 선택가능한 가장 긴 Leaf로 시작하는 것이 가장 효과적입니다.
5. 4번과 3번을 연관지으면 A라는 Leaf에서 왔다면, A를 제외한 Leaf중 상위 2개만 고려하면 됩니다.

토의

• 저는 각 Split별로 탐색을 시도하였는데, 이부분에 대해서 Subtree를 메모리에 저장할 필요가 있어보입니다. 아마도 커다란 Split 여러개 사이의 연결에 따른 처리를 위하여 Leaf처리하는 부분을 기억시킬 필요가 있지않나 생각됩니다.
  • 각 탐색을 Leaf-Split으로 시작하는 것까지는 자명한데, 여기서 [Leaf Leaf], [Leaf, Split,...], [Split(U-turn), Split]로 3가지 가능성이 존재합니다.
  • [Leaf, Leaf]는 그것으로 종결되므로 기록하지 않고, 나머지 2가지 경우에 대해서 처리해야 되는데, 깔끔한 방법이 저는 당장 생각이 나질 않습니다.